本文主要是介绍Nyoj 998 sum，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：点击打开链接
给你一个数N,使得在1~N之间能够找到x使得x满足gcd（ x , N ） >= M，求解gcd(x,N)的和
这次我们求解的是gcd(x,N)的和。有是比较简单了。
还是枚举n的因子。
假设n的因子为d。d*gcd(x/d,n/d)=1。
d*Euler(n/d)就是因子为gcd(x,n)=d，的gcd(x,n)的和。
描述不好。
直接代码：
#include <cstdio>
#include <cstring>
#include <cmath>
#define bug puts("bingo!")
using namespace std;
#define LL long long
const LL mod=1e9+7;LL Euler(LL n){LL ans=n;for(LL i=2;i<=sqrt(n);i++){if(n%i==0){while(n%i==0) n=n/i;ans=ans/i*(i-1);}}if(n>1) ans=ans/n*(n-1);return ans;
}int main(){LL n,m;while(~scanf("%lld%lld",&n,&m)){LL ans=0;for(int i=1;i*i<=n;i++){if(n%i==0){int d;if(i>=m){d=i;ans=ans+d*Euler(n/d);}if(i*i!=n&&n/i>=m){d=n/i;ans=ans+d*Euler(n/d);}}}printf("%lld\n",ans);}return 0;
}这篇关于Nyoj 998 sum的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
