U403635 鬼吹灯

给定正整数 $n(n\le 4\times 10^{16})$，请求出 $\sum_{i=0}^{n}(-1)^i\gcd(n,i)$。由于结果可能很大，只要求出该值对 $2^{64}$ 取模的结果。 其中 $\gcd(a,b)$ 表示 $a$ 和 $b$ 的最大公约数。 注意求和的范围是 $i$ 从 $0$ 到 $n$。

一行一个整数 $n$。

一行一个整数，表示问题的答案 $\bmod 2^{64}$ 的结果。

- 对于 $20\%$ 的数据，保证 $n\le 10^6$。 - 对于另外 $30\%$ 的数据，保证 $n$ 是个奇数。 - 对于 $100\%$ 的数据，保证 $n\le 4\times 10^{16}$。 注意本题特殊的时间限制。