nyoj762——分解质因数+容斥+二分

第k个互质数

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

难度：4

描述: 两个数的a，b的gcd为1，即a，b互质，现在给你一个数m，你知道与它互质的第k个数是多少吗？与m互质的数按照升序排列。

输入

输入m ，k （1<=m<=1000000;1<=k<=100000000）

输出

输出第k个数。

样例输入

样例输出

上传者

TC_常红立

#include <bits/stdc++.h>

using namespace std;

typedef long long  ll;

const int INF = 0x3f3f3f3f;

const int maxn = ;

const int moder = ;

int a[];                

void fenjie(int n)

{

    int cnt = ;

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

        if(n%i == ){

            a[++cnt] = i;                 //每个i便是n的质因数

            while(n%i == ) n = n/i;

        }

    }

    if(n > )a[++cnt] = n;

    a[] = cnt;

}

// 计算[1, n]内与m互质的数的个数

int que[<<];

int Count(int n, int m) {

    int g = , sum = n;

    que[++g] = ;

    for(int i = ; i <= a[]; ++i){

        int t = g;

        for(int j = ; j <= g; ++j){                //容斥。。

            que[++t] = que[j] * a[i] * -;

            sum += n / que[t];

        }

        g = t;

    }

    return sum;

}

int Binary_search(int m, int K){

    int l = , r = , mid;

    while(l <= r){

        mid = (l + r) >> ;

        if(Count(mid, m) >= K) r = mid - ;

        else l = mid + ;

    }

    return l;

}

int main ()

{

    int m,k;

    while(~scanf("%d%d",&m,&k)){

        memset(a,,sizeof(a));

        fenjie(m);

        int ans = Binary_search(m,k);

        printf("%d\n",ans);

    }

    return ;

}

——这题也太变态了吧，看了题解也是半懂不懂

思路：

首先要知道，

在[1,m]之间与m互质的数的个数=[1,m]之间的总个数-[1,m]之间与n不互质的数的个数

所以，要先对m进行质因数分解，求出m有哪些质因数，然后二分枚举答案mid，用容斥求[1,mid]内与m互质的数有多少个，让其结果与k比较

判断的时候，[1,mid]之间与m互质的数的数量 = mid - （包含一个质因子的数的个数）+（包含2个质因子的数的个数）-（包含3个质因子的数的个数）+（包含4个质因子的数的个数）.....

巴特西

nyoj762——分解质因数+容斥+二分

第k个互质数

最新文章

热门文章