0680 - 世界一簡単な問題 (ただしそうとは言っていない)

問題文

platypusさんは、整数 k に対して、gcd(k, l) = 1 を満たす1以上k以下の整数 l の個数 を返す関数 f(k) を定義しました。
整数 n が与えられます。n の約数 m すべてに対して、f(m) の合計を求めなさい。

制約

すべての入力データに対して、1 ≤ n ≤ 10¹⁸ を満たす。

得点

1 ≤ n ≤ 100000 を満たすテストケースにすべて正解した場合は、16点が与えられる。
すべてのテストケースに正解した場合は、追加で9点が与えられる。

入出力例

入力例

2

出力例

2

f(1) = 1 (互いに素なのは1だけ), f(2) = 1 (互いに素なのは1だけ) となります。
よって、答えは1+1=2となります。