【51NOD 1040 最大公约数之和】 GCD+欧拉函数

51nod1040最大公约数之和
题意
给出一个n，求1-n这n个数，同n的最大公约数的和。
做法
我们知道最后肯定是求n的每个因子所做的贡献，
考虑因子p的贡献是
$gcd(n,x)=p(x<=n)$
满足条件的x的个数，将上面的式子进行化简
$gca(n/p,x/p)=1$
于是这里x的出现次数就是在小于$n/p$的数字中与$n/p$互质的数的个数$*p$
于是我们只要求出$\varphi \left( n/p\right)$
所以我们只要sqrt枚举因子，计算每个因子的贡献就可以了。
注意这里$(n/p)$可能达到1e9的级别，所以我们只能用计算单个欧拉函数的方式去计算，不能预处理。
代码

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
ll phi(ll n)
{ll res=n;for(ll i=2;i*i<=n;i++){if(n%i==0){res=res-res/i;while(n%i==0)  n/=i;}}if(n>1) res=res-res/n; //可能还有大于sqrt(n)的素因子return res;
}
int main()
{ll ans=0;ll n;scanf("%lld",&n);for(ll i=1;i*i<=n;i++){if(n%i==0){ll tmp=n/i;ans+=phi(tmp)*i;if(i!=tmp) ans+=phi(i)*tmp;}}printf("%lld\n",ans);return 0;
}