POJ2773 Happy 2006
今天竟然是一道poj题目。（题目链接戳标题↑）
只写了一道题是因为其他的题我wa了
思路
首先观察这题的\(k\)的大小，一锅煮不下\(O(n)\)都扛不住，更别说你还得用辗转相除法用\(O(log(n))\)测试两个数的最大公约数了。
何以解忧，唯有二分。那么怎么二分呢，掐指一算，如果对于一个任意的自然数x，我们能求出小于他的所有与m互质的数的数量，那么我们就可以直接二分答案了！
相信学过小奥的诸位都知道如何解决这个问题了——容斥原理（详情请百度）。我们只需存下m的所有质因子，然后就可以计算以上的那个东西了。终于，这题的大体思路形成了。
代码
#include<cstdio>
long long num,l,r,m;
long long n,t=1,tot,cnt;
long long arr[10];
bool vis[10];
void dfs(int n,int l,long long va,long long mx){
if(n==0){
cnt+=mx/va;
return;
}
for(int i=l+1;i<t;i++){
if(vis[i])continue;
vis[i]=1;
dfs(n-1,i,va*arr[i],mx);
vis[i]=0;
}
}
int check(long long k){
tot=0;
for(int i=1;i<t;i++){
cnt=0;
dfs(i,0,1,k);
tot+=((i&1)?cnt:-cnt);
}
tot=k-tot;
return tot>=num;
}
int main(){
while(scanf("%lld%lld",&n,&num)!=EOF){
t=1;
if(!(n&1)){
arr[t++]=2;
while(!(n&1))
n>>=1;
}
for(long long i=3;i*i<=n;i+=2)
if(n%i==0){
while(n%i==0)
n/=i;
arr[t++]=i;
}
if(n!=1)
arr[t++]=n;
l=0;r=1e10;
while(l<r){
m=(l+r)/2;
if(check(m))r=m;
else l=m+1;
}
printf("%lld\n",l);
}
return 0;
}
总结
- 题目有多组数据，记得初始化变量呦
- 提升小奥基础（小奥万岁！）
作者：@ethan-enhe
本文为作者原创，转载请注明出处：本文链接
阅读量: