問題一覧 > 通常問題

No.3824 GCD of All

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 19
作問者 : shiomusubi496 / テスター : Rho zeta7532 okkuu
お気に入りにしたユーザー ProblemId : 14259 / 自分の提出
問題文最終更新日: 2026-11-21 15:40:43
TSG LIVE! 17 プログラミングコンテスト (順位表) の他の問題:

問題文

正整数 $M$ が与えられます。

$1 \leq N \leq M$ なる正整数 $N$ に対して、長さ $N$ で総和 $M$ の正整数列 $A=(A_1, A_2, \ldots, A_N)$ に対する $\gcd(A_1, A_2, \ldots, A_N)$ としてあり得る最大値を $f(N)$ と定義します。

$\displaystyle \sum_{N=1}^M f(N)$ を求めてください。

入力

$M$
  • $1 \leq M \leq 10^{12}$
  • 入力は全て整数

出力

$\displaystyle \sum_{N=1}^M f(N)$ を一行に出力してください。

最後に改行してください。

サンプル

サンプル1
入力
4
出力
8

それぞれの $N$ に対して、$f(N)$ は以下のようになります。

  • $N=1$:$A=(4)$ のときなどが最大で、$f(1)=4$。
  • $N=2$:$A=(2,2)$ のときなどが最大で、$f(2)=2$。
  • $N=3$:$A=(1,2,1)$ のときなどが最大で、$f(3)=1$。
  • $N=4$:$A=(1,1,1,1)$ のときなどが最大で、$f(4)=1$。

よって求める値は $4+2+1+1=8$ です。

サンプル2
入力
1
出力
1

サンプル3
入力
1000000000000
出力
25290050000000

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。