Codeforces 920G（二分+容斥）

题意：

　　定义F(x,p)表示的是一个数列{y}，其中gcd(y,p)=1且y>x

　　给出x,p,k，求出F(x,p)的第k项

　　x,p,k<=10^6

分析：

　　很容易想到先二分，再做差

　　然后问题就变成了[1,x]内有多少个数是和p互质的

　　我们可以先将p质因数分解，然后用这些数组合去在[1,x]容斥就行了

long long cal(long long x)
{
    int n=f.size();
    long long ans=0;
    for(int i=0;i<(1<<n);++i)
    {
        long long num=1;
        int sgn=1;
        for(int j=0;j<n;++j)
            if((1<<j)&i) num*=f[j],sgn*=-1;
        ans+=sgn*(x/num);
    }
    return ans;
}