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没过...很尴尬。
代码：
//2017.10.31
//math
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll ;
inline ll read();
namespace lys{
ll n,ans;
ll phi(ll x){
int i;
ll w=x,res=x;
;1LL*i*i<=w;i++){
if(!(x%i)){
res=res*(i-)/i;
while(!(x%i)) x/=i;
}
}
) res=res*(x-)/x;
return res ;
}
int main(){
int i;
n=read();
;1LL*i*i<=n;i++)
if(!(n%i)){
ans+=phi(n/i)*i;
if(1LL*i*i!=n) ans+=phi(i)*(n/i);
}
printf("%lld\n",ans);
;
}
}
int main(){
lys::main();
;
}
inline ll read(){
ll kk=,ff=;
char c=getchar();
'){
;
c=getchar();
}
+c-',c=getchar();
return kk*ff;
}