List Of Integers

题意：给你x、p、k三个数，让你求大于x的第k个与p互素的数？

思路：求出p的质因子，然后求小于等于x的与p互质的个数求出为j，题意就相当于求大于0的第k+j个与p互素的数了，二分枚举答案，求小于等于某一个数与p互质的个数使用容斥原理计算得出。

代码：

#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>

#define inf 1000000007

using namespace std;

typedef long long ll;

int x, p, k;

int prime[1000005], ji=0, shu[105], jj=1;
int pa[1000005];

int Solve(int x,int a,int type)
{
    if(a==jj)
    {
        return x * type;
    }
    else
    {
        return Solve(x,a+1,type) + Solve(x/shu[a],a+1,type * -1);
    }
}


int main()
{
    int t;
    scanf("%d",&t);
    pa[0]=pa[1]=1;
    for(int i=2; i*i<=1000000; i++)
    {
        if(!pa[i])
        {
            prime[ji++]=i;
            for(int j=i*i; j<=1000000; j=j+i)
            {
                pa[j]=1;
            }
        }
    }
    for(int i=1000;;i++)
    {
        if(!pa[i])
        {
            prime[ji++]=i;
            break;
        }
    }
    while(t--)
    {
        jj=1;
        scanf("%d%d%d",&x,&p,&k);
        for(int i=0; prime[i]*prime[i]<=p; i++)
        {
            int flag=1;
            while(p%prime[i]==0)
            {
                if(flag)
                {
                    flag=0;
                    shu[jj++]=prime[i];
                }
                p=p/prime[i];
            }
        }
        if(p>1)
        shu[jj++]=p;
        if(p==1&&jj==0)
        {
            printf("%d\n",x+k);
            continue;
        }
        k=k+Solve(x,1,1);
        int l=x, r=1000000005;
        while(r-l>1)
        {
            int mid=(l+r)/2;
            if(Solve(mid,1,1)>=k)
            {
                r=mid;
            }
            else
            {
                l=mid;
            }
        }
        cout << r << endl;
    }
    return 0;
}