最大公约数之和 51Nod - 1040

本文主要是介绍最大公约数之和 51Nod - 1040，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

https://www.51nod.com/Challenge/Problem.html#!#problemId=1040

求所有gcd之和 就看n的每个因子会做出多少贡献即可 即对n的某个因子x 有贡献的i满足gcd(n,i)=x 从而推出gcd(n/x,i/x)=1

这样问题就转换为 对每个因子x求n/x的欧拉函数值了

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;ll pre[maxn];
ll n;
int tot;ll geteular(ll p)
{ll res,i;res=p;for(i=2;i*i<=p;i++){if(p%i==0){res=(res*(i-1))/i;while(p%i==0) p/=i;}}if(p!=1) res=(res*(p-1))/p;return res;
}int main()
{ll ans,i;scanf("%lld",&n);for(i=1;i*i<=n;i++){if(n%i==0){pre[++tot]=i;if(i*i!=n) pre[++tot]=n/i;}}ans=0;for(i=1;i<=tot;i++) ans+=geteular(n/pre[i])*pre[i];printf("%lld\n",ans);return 0;
}

 

这篇关于最大公约数之和 51Nod - 1040的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---