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=;

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

     {

         long long num=;

         int sgn=;

         for(int j=;j<n;++j)

             if((<<j)&i) num*=f[j],sgn*=-;

         ans+=sgn*(x/num);

     }

     return ans;

 }

巴特西

Codeforces 920G（二分+容斥）

最新文章

热门文章