给出一个n，求1-n这n个数，同n的最大公约数的和。比如：n = 6
1,2,3,4,5,6 同6的最大公约数分别为1,2,3,2,1,6，加在一起 = 15
输入
1个数N(N <= 10^9)
输出
最大公约数之和
输入样例
6
输出样例
15
思路：n最大公约数之和（用sum表示）是有他的因数求得，我们只要求得对应因数有多少个。
比如 6 因数： 1 2 3 6
个数： 2 2 1 1
答案就是 1*2+2*2+3*1+6*1
怎么求个数呢？
如果如果暴力求解我们会这样做：遍历1~n求每个最大公约数相加
即 for(int i=1;i<=n;i++)
sum+=gcd(i,n)
很显然会超时。
我们假设 gcd(i,n)=v （i是1~n） v一定是n的因数。
我们要求的就是v的个数。
可以转换成求gcd(i/v,n/v)=1个数 (i/v是0~n/v ) n/v也是n的因数
答案就是sum（p*phi(n/p)）了(p是因子，phi（）是欧拉函数,sum是求和)。
代码：
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #define ll long long using namespace std; ll eular(ll n)//欧拉函数模板 { ll ans=n; for(int i=2;i*i<=n;i++) { if(n%i==0) { ans-=ans/i; while(n%i==0) n/=i; } } if(n>1) ans-=ans/n; return ans; } int main() { ll n; while(cin>>n) { ll ans=0; for(ll i=1;i*i<=n;i++) { if(n%i==0)//i是n的因子 { ans+=i*eular(n/i);//因子v 乘以个数 (1-n/v与n/v互质的个数) if(n!=i*i)// n/v是n的因子,不要漏算了 ans+=n/i*eular(i); } } cout<<ans<<endl; } return 0; }