POJ2773Happy 2006解题报告

这道题有很多人用欧拉函数做的，我用的是容斥定理，要找第k个和m互素的数，先二分答案，然后用容斥定理计算在1-ans之间有多少个与m互素的元素，这里要用到容斥定理，

假设1到mid中有k个与m互素，而且mid是最小的一个，那么我们就可以说mid是第k个与m互素的数。。

这样就可以用到2分的思想，讲1到inf进行2分，2分出最小的符合有k个与m互素的数的数就行了。。。

对于就1到mid中有多少个与m互素的数需要用到容斥原理：

比如假设m=12；mid=13

12=2*2*3

那么1到mid中与m不互质的数就有2,3,4,6,8,9,10,12，

其实就是2的所有倍数，以及3的所有倍数

这样我们就算出与1到13中与12不互素的个数为： 13/2+13/3-13/(2*3)=8;

互素的数就位13-8=5；

View Code

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #define N 1000005
 5 #define inf 0x7fffffff
 6 using namespace std;
 7 typedef long long LL;
 8 bool isprime[N];
 9 LL prime[N];
10 LL d[30],f;//这里开到30是因为即使按照最小的素数2来划分，也不会超过20个素因子
11 int cnt;
12 void init()
13 {
14     cnt=0;
15     LL i,j;
16     memset(isprime,true,sizeof(isprime));
17     for(i=2;i<=N-5;i++)
18     {
19         if(isprime[i])
20         {
21             prime[cnt++]=i;
22             for(j=i*i;j<=N-5;j+=i)
23             isprime[j]=false;
24         }
25     }
26 }
27 void dfs(LL cur,LL now,LL mid,bool neg,LL &res)//容斥定理的搜索
28 {
29     if(cur>=f)
30     return;
31     LL n=now*d[cur];
32     dfs(cur+1,now,mid,neg,res);//不乘的情况
33     if(neg)
34     res+=(mid/n);
35     else
36     res-=(mid/n);
37     dfs(cur+1,n,mid,!neg,res);//乘的情况
38 }
39 LL sum(LL mid)
40 {
41     LL res=0;
42     dfs(0,1,mid,true,res);
43     return mid-res;
44 }
45 int main()
46 {
47     LL m,k,i,j,low,high,mid,ans,temp;
48     init();
49     while(scanf("%lld%lld",&m,&k)!=EOF)
50     {
51         f=0;
52         for(i=0;i<cnt;i++)
53         {
54             if(m%prime[i]==0)
55             {
56                 d[f++]=prime[i];
57                 while(m%prime[i]==0)
58                 m/=prime[i];
59             }
60             if(m==1)
61             break;
62         }
63         low=1,high=inf;
64         while(low<=high)
65         {
66             mid=(high-low)/2+low;
67             temp=sum(mid);
68             if(temp==k)
69             ans=mid;
70             if(temp>=k)
71             high=mid-1;
72             else
73             low=mid+1;
74         }
75         printf("%lld\n",ans);
76     }
77     return 0;
78 }