#include<stdio.h>
#include<math.h>
#include<string.h>
const int M=2147483200;
int gene[30],t;
int part[30],tp;
bool used[30];
void dfs(int cur,int depth,int &cnt,int tmp)
{
	int i,sum;
	if (cur>depth) 
	{
		sum=1;
		for(i=0;i<=depth;i++)
			sum*=part[i];
		if (depth%2==0) cnt+=tmp/sum;
		else cnt-=tmp/sum;
		return ;
	}
	for(i=cur;i<=t-depth+cur;i++)
		if (used[i])
		{
			used[i]=false;
			part[cur]=gene[i];
			dfs(cur+1,depth,cnt,tmp);
			used[i]=true;
		}
}
int work(int tmp)
{
	int cnt,i;
	cnt=0;
	for(i=0;i<=t;i++)
	{
		memset(used,true,sizeof(used));
		dfs(0,i,cnt,tmp);
	}
	return cnt;
}
int Bsearch(int k)
{
	int front,rear,tmp,mid;
	front=1;	rear=M;
	while(front<=rear)
	{
		mid=(front+rear)/2;
		tmp=mid-work(mid);
		if (tmp==k) 
		{
			while (mid>1 && k==mid-1-work(mid-1)) mid--;
			return mid;
		}
		if (tmp>k) rear=mid-1;
		else front=mid+1;
	}
	return -1;
}
int main()
{
	int m,k,p,i;
	while(scanf("%d%d",&m,&k)!=EOF)
	{
		p=int(sqrt(m));
		t=-1;
		for(i=2;i<=p;i++)
			if (m%i==0)
			{
				gene[++t]=i;
				while(m%i==0) m/=i;
			}
		if (m>1) gene[++t]=m;

		printf("%d\n",Bsearch(k));
	}
	return 0;
}
		

• Re:实在受不了了，我辛辛苦苦的写了个容斥原理，然后2分，不知道为什么wa,过了论坛里的数据，并且跟ac的code，测试了一下，答案基本一样，不知道有什么数据过不了，高手指点一下，代码内附 (53) o_oXo_o 2006-07-14 22:08:26
  • 谢谢了，现在已经ac,原来dfs生成c(n,k)序列的时候，有个小错误。 (0) bluewind 2006-07-14 22:49:09