题目大意

给定正整数 N (1 <= N <= 1000000) 和 K (1 <= K <= 100000000),求与N互质的第K个数。多组数据。

解题思路

在此提供两种解题思路。
思路 1 (gcd函数的性质):
a,b两数互质,当且仅当gcd(a,b) = 1。
由gcd函数的性质我们可以知道,gcd(a,b) = gcd(a+b,b)。
那么在[1,N]中与N互质的数加上若干倍N,任会与N互质,同理,在[1,N]中与N不互质的数加上若干倍N,任不会与N互质。
我们就只需求出[1,N]中与N互质的数集,通过加若干倍N即可得到答案。
复杂度O(T×N).
----------------华丽分割线-----------------
思路 2 (容斥原理):
现在让我们来考虑这样一个问题:给定正整数 X,Y,问 1~N 中有多少个数与 Y 互质?
我们可以对 Y 进行质因数分解,得到 Y 的质数集和。这一步可以通过O(n)预处理(即线性筛),单词分解O(logn)。
那么就可以用容斥原理求出 1~N 中有多少个数与Y互质。
我们就可以通过二分答案将原问题转化为判定性问题,从而求解。
复杂度O(T×log2^64×2^loglogN),2^64为答案上界,loglogN 为 X 的质因子个数级别,那个2的次方是容斥的代价。

代码

解法 1:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

#define MAXN 1000005
using namespace std;
typedef unsigned long long LL;
int N, K;
int co[MAXN], cnt, num;

inline int gcd(int a,int b) {
    return b==0? a: gcd(b,a%b);
}

void Solve() {
    cnt = 0;
    for(int i=1; i<=N; i++)
        if(gcd(i, N) == 1)
            co[++cnt] = i;
    num = K/cnt;
    K = K % cnt;
    if(K==0) num--, K=cnt;
    cout<<((LL)num*(LL)N) + (LL)co[K]<<endl;
}

int main()
{
    while(scanf("%d%d", &N, &K) != EOF) Solve();
    return 0;
}

解法 2:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define MAXN 1000005
using namespace std;
typedef long long LL;
int p[MAXN>>2], pt=0;
int m[MAXN];
int N, K, num;
int a[100], cnt; //a为质因子集合
LL Ans, ji;
int get[100];

void Build_prime() {
    memset(m, 0, sizeof(m));
    p[++pt] = 2;
    for(int i=2; i<=1000000; i++) {
        if(!m[i]) p[++pt] = i;
        for(int j=1; j<=pt; j++) {
            if(p[j] * i > 1000000) break;
            m[p[j] * i] = p[j];
        }
    }
}

void fenjie(int n) {
    for(int i=0; i<=50; i++) a[i] = 0;
    cnt = 0;
    while(m[n] > 0) {
        if(m[n] > a[cnt]) a[++cnt] = m[n];
        n = n / m[n];
    }
    if(n > a[cnt]) a[++cnt] = n;
}

void DFS(int p, LL n) {
    get[p] = 2;
    while(get[p] > 0) {
        get[p]--;
        if(p == cnt) {
            num = 0;
            ji = 1;
            for(int i=1; i<=cnt; i++)
            if(get[i] == 1) {
                ji = ji * (LL)a[i];
                num++;
            }
            if(num > 0) {
                if(num & 1) Ans += (LL)(n/ji);
                else Ans -= (LL)(n/ji);
            }
        } else DFS(p + 1, n);
    }
}

int main()
{
    Build_prime();
    while(scanf("%d%d", &N, &K) != EOF)
    {
        if(N == 1) { printf("%d\n", K); continue; }
        fenjie(N);
        Ans = 0;
        LL l=1, r=(LL)10000000000;
        while(l <= r) {
            LL mid = (l+r)>>1;
            Ans = 0;
            DFS(1, mid);
            Ans = mid - Ans;
            if(Ans >= K) r = mid - 1;
            else l = mid + 1;
        }
        printf("%lld\n", l);
    }
    return 0;
}