学步园

题目链接：点击打开链接

给你一个数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;
}