学步园

题目链接：点击打开链接

题意：给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;
}

数论需要继续学习。。。。。。