Longge的问题
Description
Longge的数学成绩非常好，并且他非常乐于挑战高难度的数学问题。现在问题来了：给定一个整数N，你需要求出∑gcd(i, N)(1<=i <=N)。
Input
一个整数，为N。
Output
一个整数，为所求的答案。
Sample Input
6
Sample Output
15
HINT
【数据范围】
对于60%的数据，0<N<=2^16。
对于100%的数据，0<N<=2^32。
注意到这些最大公约数肯定是n的约数，对于约数K，我们想找出gcd（n，i）=k的有多少个，也即gcd（n/k，i/k）=1，也就等价于求φ（n/k）。
ans=Σφ（n/k）*k
问题就在于怎么求φ（n），之前竟然一直不知道可以sqrt（n）计算，感觉自己好傻，今天学习了...（一直以为要用递推，不然就要写线性筛[神经病啊]）
还有就是枚举sqrt（n）时注意k*k=n的情况，没判这种情况结果bzoj过了，luogu没过...很尴尬。
代码：
1 //2017.10.31 2 //math 3 #include<iostream> 4 #include<cstdio> 5 #include<cstring> 6 using namespace std; 7 typedef long long ll ; 8 inline ll read(); 9 namespace lys{ 10 ll n,ans; 11 ll phi(ll x){ 12 int i; 13 ll w=x,res=x; 14 for(i=2;1LL*i*i<=w;i++){ 15 if(!(x%i)){ 16 res=res*(i-1)/i; 17 while(!(x%i)) x/=i; 18 } 19 } 20 if(x>1) res=res*(x-1)/x; 21 return res ; 22 } 23 int main(){ 24 int i; 25 n=read(); 26 for(i=1;1LL*i*i<=n;i++) 27 if(!(n%i)){ 28 ans+=phi(n/i)*i; 29 if(1LL*i*i!=n) ans+=phi(i)*(n/i); 30 } 31 printf("%lld ",ans); 32 return 0; 33 } 34 } 35 int main(){ 36 lys::main(); 37 return 0; 38 } 39 inline ll read(){ 40 ll kk=0,ff=1; 41 char c=getchar(); 42 while(c<'0'||c>'9'){ 43 if(c=='-') ff=-1; 44 c=getchar(); 45 } 46 while(c>='0'&&c<='9') kk=kk*10+c-'0',c=getchar(); 47 return kk*ff; 48 }