BZOJ2705[SDOi2012]Longge的问题

题面十分简洁：

0<N<=2³²

解析：

依次枚举i肯定会超时。

由于gcd(i,N)|N，所以可以考虑枚举gcd(i,N)，即N的约数，设为d，对答案的贡献就是。

又，所以d的贡献为

答案就是

最后，Libreoffice的公式编辑器真好用。

代码如下：

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <iostream>
  4 #include <cmath>
  5 using namespace std;
  6 
  7 typedef unsigned long long ULL;
  8 typedef long long LL;
  9 typedef pair<int, int> pii;
 10 typedef pair<LL, LL> pll;
 11 
 12 LL phi(LL);
 13 
 14 int main() {
 15 	LL N, ans = 0;
 16 	scanf("%lld", &N);
 17 	for (LL i = 1; i * i <= N; i++)
 18 		if (N % i == 0) {
 19 			ans += (N / i) * phi(i);
 20 			if (N != i * i) ans += i * phi(N / i);
 21 		}
 22 	printf("%lld", ans);
 23 
 24 	return 0;
 25 }
 26 
 27 LL phi(LL x) {
 28 	LL res = x;
 29 	for (LL i = 2LL; i * i <= x; i++)
 30 		if (x % i == 0) {
 31 			res = res / i * (i - 1);
 32 			while (x % i == 0) x /= i;
 33 		}
 34 	if (x > 1) res = res / x * (x - 1);
 35 	return res;
 36 }

AC代码