D - Sum of (-1)^f(n) /

Time Limit: 7 sec / Memory Limit: 2048 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) = 0f(2) = 1f(3) = 1f(4) = 2f(5) = 1f(6) = 2 なので,答えは (-1)^0 + (-1)^1 + (-1)^1 + (-1)^2 + (-1)^1 + (-1)^2 = 0 である.


入力例 2

2019

出力例 2

-25

入力例 3

906150257

出力例 3

1