nyoj998——欧拉+折半查找

Sum

时间限制：1000 ms | 内存限制：65535 KB

难度：3

描述

给你一个数N,使得在1~N之间能够找到x使得x满足gcd（ x , N ） >= M，

求解gcd(x,N)的和

输入

多组测试数据

每行输出两个数N，M（N,M不超int）

输出

输出sum

样例输入

5 3

样例输出

上传者

ACM_张书军

#include <bits/stdc++.h>

using namespace std;

typedef long long  ll;

const int INF = 0x3f3f3f3f;

const int maxn = ;

const int moder = ;

ll eular(ll n)

{

    ll ans = n;

    for(int i=;i*i <= n;i++){

        if(n%i == ){

            ans = ans - ans/i;

            while(n%i == )

                n = n/i;

        }

    }

    if(n > )

        ans = ans - ans/n;

    return ans;

}

int main()

{

    ll n,m;

    while(scanf("%lld%lld",&n,&m)!=EOF){

        ll res = ;

        for(int i=;i*i <= n;i++) {

            if (n % i == ) {

                if (i >= m) {

                    res += i * eular(n / i);

                }

                if (i * i != n && n / i >= m){

                    res += n/i*eular(i);

                }

            }

        }

        printf("%lld\n",res);

    }

    return ;

}

————很巧妙的运用了欧拉函数

巴特西

nyoj998——欧拉+折半查找

Sum

最新文章

热门文章