D - Sum of (-1)^f(n)
解説
/
実行時間制限: 7 sec / メモリ制限: 2000 MB
配点: 100 点
Xmas Contest 2013 問題 G を見たくろうさ「10^9 って (笑) 符号だけって (笑)」
問題文
正の整数 n に対し,f(n) を n が持つ素因数を重複を込めて数えた個数とする.例えば,200 = 2^3 \times 5^2 なので,f(200) = 5 となる.
正の整数 N が与えられるので,\sum_{n=1}^N (-1)^{f(n)} を求めよ.
制約
- 1 \le N \le 10^{11}.
部分点
- N \le 10^{10} を満たすデータセットに正解した場合は,45 点が与えられる.
- 追加制約のないデータセットに正解した場合は,上記とは別に 55 点が与えられる.
入力
N
出力
\sum_{n=1}^N (-1)^{f(n)} の値を 1 行に出力せよ.
入力例 1
6
出力例 1
0
f(1) = 0,f(2) = 1,f(3) = 1,f(4) = 2,f(5) = 1,f(6) = 2 なので,答えは (-1)^0 + (-1)^1 + (-1)^1 + (-1)^2 + (-1)^1 + (-1)^2 = 0 である.
入力例 2
2019
出力例 2
-25
入力例 3
906150257
出力例 3
1