No.3651 K-th Sum of Divisors
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 1024 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 59
作問者 :
Rino-program
/ テスター :
gomaazarasi
p-adic
とある理系大学生の日常
タグ : / 解いたユーザー数 59
作問者 :
Rino-program
/ テスター :
gomaazarasi
p-adic
とある理系大学生の日常
問題文最終更新日: 2026-08-12 16:23:24
問題文
正整数 $N$ と、正整数 $K$ が与えられます。
ある正整数 $x$ に対して、$x$ のすべての正の約数の和を $100003$ で割った余り（$\bmod 100003$）を $f(x)$ と定義します。
長さ $K$ の数列 $A=(A_1,\ldots,A_K)$ を以下のように定めます。
- $A_1 = N$
- $A_{i+1} = f(A_i)$ （$i$ は $1$ 以上 $K-1$ 以下の正整数）
このとき、数列の $K$ 番目の項である $A_K$ の値を求めてください。
なお、この問題の制約下で $K$ 以下の正整数 $z$ で $A_z = 0$ となる $z$ は存在しない事が保証されます。
制約
- $1 \leq N \leq 3 \times 10^6$
- $1 \leq K \leq 10^{18}$
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
$N$ $K$
出力
$A_K$ の値を $1$ 行に出力してください。
最後に改行してください。
サンプル
サンプル1
入力
6 1
出力
6
$A_1 = 6$ です。
サンプル2
入力
6 2
出力
12
$A_1 = 6$ であり、$A_2 = f(6) = (1 + 2 + 3 + 6) \bmod 100003 = 12$ となります。
サンプル3
入力
6 3
出力
28
$A_3 = f(A_2) = f(12) = (1 + 2 + 3 + 4 + 6 + 12) \bmod 100003 = 28$ となります。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。