本文主要是介绍E 求1-n与n的最大公约数大于m的和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：点击打开链接
题意：给n，m。求x(1<=x<=n)的和，其中gcd(x,n)>=m。
学习了，一个欧拉函数求和的问题。
Euler_sum(n)=n*Euler(n)/2；也就是求的与n互质的数的和。。
代码：
LL Euler_sum(LL n){if(n==1) return 1;//n==1时候，需要特判。else return n*Euler(n)/2;
}对该题的话。
我们需要做的就是，枚举n的因子。寻找gcd(x,n)=n的因子。
假设n的因子为d(d>=m)，也就说求gcd(x,n)=d。我们知道d*gcd(x/d,n/d)=1;n/d和x/d是互质的。
说也就是求1-n/d内与n/d互质的和。乘以一个d就是x，gcd(x,n)=d和。
表述不清。
直接代码：
#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;
}LL Euler_sum(LL n){if(n==1) return 1;else return n*Euler(n)/2;
}int main(){int T;scanf("%d",&T);while(T--){LL n,m,ans=0;scanf("%lld%lld",&n,&m);for(int i=1;i*i<=n;i++){if(n%i==0){int d;if(i>=m){d=i;ans=(ans+d*Euler_sum(n/d))%mod;}if(i*i!=n&&n/i>=m){d=n/i;ans=(ans+d*Euler_sum(n/d))%mod;}}}printf("%lld\n",ans%mod);}return 0;
}
数论需要继续学习。。。。。。
这篇关于E 求1-n与n的最大公约数大于m的和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
