bzoj2705/sdoi2012 Longge的问题（欧拉函数

Description

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

Input

一个整数，为N。

Output

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

Sample Input

6

Sample Output

15

HINT

0<N<=2^32。

分析

考虑枚举 $d=gcd(i,n)$d=gcd(i,n)
于是有 $\sum _{i=1}^{n}gcd(i,n)=\sum _{d\mid n}d\ast \sum _{i=1}^n\left[gcd\right(i,n)==d]=\sum _{d\mid n}d\ast \sum _{i=1}^n\left[gcd\right(i/d,n/d)==1]$i=1∑n​gcd(i,n)=d∣n∑​d∗i=1∑n​[gcd(i,n)==d]=d∣n∑​d∗i=1∑n​[gcd(i/d,n/d)==1]
注意到 $i/d\&lt;=n/d$i/d<=n/d，于是原式等价为求 $\sum _{d\mid n}d\phi \left(n/d\right)$d∣n∑​dφ(n/d)
$O\left(\sqrt{n}\right)$O(n ​)求 $n$n 的约数即可。

代码如下

#include <bits/stdc++.h>
#define LL long long
using namespace std;
LL ans, z = 1, n;
LL phi(LL x){
	int i;
	LL ret = x;
	for(i = 2; z * i * i <= x; i++){
		if(x % i == 0){
			while(x % i == 0) x /= i;
			ret = ret / i * (i - 1);
		}
	}
	if(x > 1) ret = ret / x * (x - 1);
	return ret;
}
int main(){
	int i, j, m;
	scanf("%lld", &n);
	for(i = 1; z * i * i <= n; i++){
		if(n % i == 0){
			ans += i * phi(n / i);
			if(n != z * i * i) ans += (n / i) * phi(i);
		}
	}
	printf("%lld", ans);
	return 0;
}