[BZOJ 2705] [SDOI 2012] Longge的问题

Description

Longge的数学成绩非常好，并且他非常乐于挑战高难度的数学问题。现在问题来了：给定一个整数 \(N\)，你需要求出 \(\sum gcd(i, N)(1\le i \le N)\)。

Input

一个整数，为 \(N\)。

Output

一个整数，为所求的答案。

Sample Input

Sample Output

HINT

\(0<N\le 2^{32}\)

Solution

\[\begin{eqnarray}
\sum_{i = 1}^{n}\gcd(i,n)&=&\sum_{d\mid n}d\sum_{i=1}^{n}[\gcd(i,n)=d]\\
&=&\sum_{d|n}d\sum_{i=1}^{\frac{n}{d}}[\gcd(i,\frac{n}{d})=1]\\
&=&\sum_{d\mid n}d\times\varphi\left(\frac{n}{d}\right)
\end{eqnarray}
\]

设 \(p\) 为质数，有 \(\varphi(p^k)=p^k-\dfrac{p^k}{p}=p^k(1-\dfrac{1}{p})\)，因此

\[\begin{eqnarray}
\varphi(n)&=&\varphi(p_1^{k_1})\varphi(p_2^{k_2})\varphi(p_3^{k_3})\cdots\\
&=&p_1^{k_1}(1-\frac{1}{p_1})p_2^{k_2}(1-\frac{1}{p_2})p_3^{k_3}(1-\frac{1}{p_3})\cdots\\
&=&n(1-\frac{1}{p_1})(1-\frac{1}{p_2})(1-\frac{1}{p_3})\cdots
\end{eqnarray}
\]

因此就有了 \(O(\sqrt n)\) 求 \(\varphi(n)\) 的做法。

〖推论〗当 \(n\) 为奇数时，\(\varphi(n)=\varphi(2n)\)。

Code

#include <cstdio>

#include <cmath>

typedef long long LL;

const int N = 65540;

int phi[N], p[N], tot, np[N], m; LL n, ans;

void euler(int n) {

	phi[1] = 1;

	for (int i = 2; i <= n; ++i) {

		if (!np[i]) p[++tot] = i, phi[i] = i - 1;

		for (int j = 1; j <= tot && i * p[j] <= n; ++j) {

			np[i * p[j]] = 1;

			if (i % p[j] == 0) { phi[i * p[j]] = phi[i] * p[j]; break; }

			phi[i * p[j]] = phi[i] * (p[j] - 1);

		}

	}

}

LL getphi(LL n) {

	int m = sqrt(n); LL res = n;

	for (int i = 1; i <= tot && p[i] <= m; ++i)

		if (n % p[i] == 0) {

			res -= res / p[i];

			while (n % p[i] == 0) n /= p[i];

		}

	if (n > 1) res -= res / n;

	return res;

}

int main() {

	scanf("%lld", &n), m = sqrt(n), euler(m);

	for (int i = 1; i <= m; ++i)

		if (n % i == 0) ans += i * getphi(n / i) + (n / i) * phi[i];

	if (1LL * m * m == n) ans -= 1LL * m * phi[m];

	printf("%lld\n", ans);

	return 0;

}

巴特西