← 返回题目列表

AtCoder · pakencamp_2024_day1_g

G. 序列

中文机器翻译题面 查看原题

配点 : 400 点

問題文

满足以下条件的序列 A 的 M 项目 998244353 求余数。

  • A_{1} = N
  • 正整数k查找A_{k+1} = A_{k} + f(A_{k})

在这里, 表示不是f(x) 在 x 的 x 的最大除数。 来自

制約

  • 2 \leq N \leq 10^{12}
  • 1 \leq M \leq 10^{18}
  • 所有输入均为整数 不是

入力

输入是按以下格式从标准输入给出的。

N M

出力

数列 A 的 M 项目 998244353 后的余数。


入力例 1

4 3

出力例 1

9

A_1=4 。

f(4)=2 捻, A_2=A_1+f(A_1)=4+2=6 。

f(6)=3 捻, A_3=A_2+f(A_2)=6+3=9 。

因此,要回答的值为 9 。


入力例 2

3 1

出力例 2

3