cf920G List Of Integers 二分+容斥

题意:

求第k个大于x且与p互素的数,其中k,p,x<=1e6.

思路:

二分+容斥.

二分这个数是mid,然后去检验(x,mid]间有多少个与p互素的数.可以用容斥算出[1,mid]和[1,x]区间内有多少与p互质的数.

代码:

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int MAXN=20;
 4 int prime[MAXN],tot;
 5 int x,p,k;
 6 int getCnt(int num){
 7     int res=num;
 8     for(int i=1;i<(1<<tot);++i){
 9         int flag=0;
10         int muti=1;
11         for(int j=0;j<tot;++j){
12             if((1<<j)&i){
13                 ++flag;
14                 muti*=prime[j];
15             }
16         }
17         if(flag&1)res-=num/muti;
18         else res+=num/muti;
19     }
20     return res;
21 }
22 int qwq;
23 bool isok(int mid){
24     //printf("getCnt(%d)=%d -%d=%d
",mid,getCnt(mid),qwq,getCnt(mid)-qwq);
25     return getCnt(mid)-qwq>=k;
26 }
27 int main(){
28     int t;scanf("%d",&t);
29     while(t--){
30         scanf("%d%d%d",&x,&p,&k);
31         if(p==1){
32             printf("%d
",x+k);
33             continue;
34         }
35         int tmp=p;
36         tot=0;
37         for(int i=2;i*i<=tmp;++i){
38             if(tmp&&tmp%i==0)prime[tot++]=i;
39             while(tmp&&tmp%i==0)tmp/=i;
40         }
41         if(tmp>1)prime[tot++]=tmp;
42 
43         qwq=getCnt(x);
44     //    printf("qwq=%d
",qwq);
45         int lo=x,hi=2e7;
46         while(hi-lo>1){
47             int mid=(hi+lo)/2;
48             if(isok(mid))hi=mid;
49             else lo=mid;
50         }
51         printf("%d
",hi);
52     }
53     return 0;
54 }

View Code

其实在比赛中是想到了这个想法的,但没有很好的估计上界,在2e7范围内有至少127w个素数.上界2e7就够了.

其次还有一个问题,在比赛中我在想这样一个问题,我check的mid如果与p满足gcd(p,mid)!=1该怎么办,其实不会有这个问题, l....mid l为离mid最近且gcd(l,p)=1,他们中间的数与p互素的数都是一样的.我们相当于二分找满足条件的最小值.

关于素数计数其实还有一个东西叫素数计数函数,写起来会简单一些.