Find All Root(extra)

2 secs 1024 MB
hide's icon hide

問題文

素数PPが与えられます。この時PPの原子根の総和をansansとします。 ansansPPで割ったあまりを求めてください。

制約

PPは素数

1P10121\le P \le 10^{12}

出力

答えを1行に出力してください。 最後に改行してください。

C/C++の言語を使用する際、想定解法では64bit整数型の演算では収まらないので、 __int128型を用いることを推奨します

サンプル

入力1
13
出力1
0

全部で2,6,7,112, 6, 7, 1144つあります。すなわち、総和は2626ですので、1313で割ったあまり00を出力します。

入力2
2
出力2
1

r=1r = 1p=2p = 2の原子根とします。

入力3
37
出力3
0

総和の222222P=37P = 37で割ったあまりは00です。

Submit


Go (1.21)