和小哥哥一起刷洛谷(11)

二分答案进阶二

Posted by ethan-zhou on March 21, 2019

POJ2773 Happy 2006

今天竟然是一道poj题目。(题目链接戳标题↑) 只写了一道题是因为其他的题我wa了

思路

首先观察这题的的大小,一锅煮不下都扛不住,更别说你还得用辗转相除法用测试两个数的最大公约数了。

何以解忧,唯有二分。那么怎么二分呢,掐指一算,如果对于一个任意的自然数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
本文为作者原创,转载请注明出处:本文链接