龙哥的问题
这题思路清晰就好了.
最大公约数即为因子,我们把n的因子求出来即可,然后根据欧拉的定理即是答案了.
我们知道求gcd(1a,n)=i.就等同于gcd(1a/i,n/i)=1.
然后就是统计答案了.
代码如下:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e3;
ll ys[N];
inline ll get_phi(ll x)//得到x的欧拉函数.
{
ll cnt=x;
for(ll i=2;i*i<=x;i++)
{
if(x%i==0)
{
while(x%i==0) x/=i;
cnt=cnt/i*(i-1);
}
}
if(x>1)
{
cnt=cnt/x*(x-1);
}
return cnt;
}
int main()
{
ll n,cnt=0,ans=0;
cin>>n;
for(ll i=1;i*i<=n;i++)
{
if(n%i==0) {ys[cnt++]=i;if(i==n/i) continue;ys[cnt++]=n/i;}
}
for(ll i=0;i<cnt;i++)
{
ans+=ys[i]*get_phi(n/ys[i]);
}
cout<<ans<<endl;
return 0;
}lpt的小屋 文章被收录于专栏
我想要一份甜甜的爱情
