Description

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

Input

一个整数,为N。

Output

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

Sample Input

6

Sample Output

15

HINT

0<N<=2^32。

分析

考虑枚举 d = g c d ( i , n ) d = gcd(i,n) d=gcd(i,n)
于是有 <munderover> i = 1 n </munderover> g c d ( i , n ) = <munder> d n </munder> d <munderover> i = 1 n </munderover> [ g c d ( i , n ) = = d ] = <munder> d n </munder> d <munderover> i = 1 n </munderover> [ g c d ( i / d , n / d ) = = 1 ] \sum\limits_{i=1}^{n} gcd(i,n) = \sum\limits_{d|n}d*\sum\limits_{i=1}^{n}[gcd(i,n)==d]\\=\sum\limits_{d|n}d*\sum\limits_{i=1}^{n}[gcd(i/d,n/d)==1] i=1ngcd(i,n)=dndi=1n[gcd(i,n)==d]=dndi=1n[gcd(i/d,n/d)==1]
注意到 i / d &lt; = n / d i/d &lt;= n/d i/d<=n/d,于是原式等价为求 <munder> d n </munder> d φ ( n / d ) \sum\limits_{d|n}d\varphi(n/d) dndφ(n/d)
O ( n ) O(\sqrt{n}) O(n ) 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;
}