1136414_ac_61ms_1016k.cpp

北京大学ACM 2773 对初学者有很大帮助！

//应用欧拉函数
//gcd(x,y)=1 则 gcd(x+y,y)=1
//gcd(x,y)>1 则 gcd(x+y,y)>1
#include<stdio.h>
#include<memory.h> 
#include<math.h>
int m, k, ftop;
const int len = 1000001;
bool ok[len];
int fact[1000];
int cand[len];
int main()
{
	    int i, j;
		while(scanf("%d %d",&m,&k)!=EOF)
		{
			memset(ok, false, m + 1);
			ftop = 0;
			int tm = m;
			int euler = m;
			const int t = sqrt(tm); 
			for (i=2; i<=t&&i<=tm; i++)
			{
				if (tm%i==0)  
				{
					fact[ftop++]=i;
					euler = euler/i*(i - 1);
					while (tm%i==0) tm/=i;
				}
			}
			if (tm > 1) 
			{
				fact[ftop++] = tm; 
				euler = euler/tm*(tm - 1);
			}			
			for(i = 0; i < ftop; i ++)
			{
				if(m%fact[i] == 0)
				for(j = fact[i]; j <= m ; j += fact[i])
						ok[j] = true;
			}  
			int loop = (k - 1)/euler;
			int index = 1 + (k - 1)%euler;
			int ct = 0;
			for(i = 1; i <= m; i ++)
			{
				if(!ok[i])
				{
					ct ++;
					if(ct == index)
						printf("%d\n",i + loop*m);
				}				
			}			
		}
		return 0;
}