http://poj.org/problem?id=2773
题意：输入n,k，求与n不互素的第k个数，k可能大于n。
思路：以n=6为例，与6互素的数有一定规律。{1,5},{7,12},{13,18}......，发现在[1,n],[n+1,n*2]......[m*n+1,(m+1)*n]区间内素数个数相同，且对应位置的数都相差n的整数倍。因此只要求出[1,n]内的与n互素的数即可。这个过程没必要一个一个枚举，可以用欧拉函数解决。因为欧拉函数已经求出了n的所有质因子，与n不互素的数都与n有相同的质因子公约数，可以用这些质因子的整数倍去标记与n不互素的数。然后在线性时间内的求第k个与n互素的数。
#include <stdio.h>
#include <iostream>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#include <string>
#include <stdlib.h>
#include <algorithm>
#define LL long long
#define _LL __int64
#define eps 1e-12
#define PI acos(-1.0)
using namespace std;
const int maxn = 1000010;
int n,k,kk;
int flag[maxn];
//求Eular(n)，同时求出n的质因子，用这些质因子标记与n不互素的数。
int Eular(int n)
{
int ret = n,m = n;
memset(flag,0,sizeof(flag));
for(int i = 2; i*i <= n; i++)
{
if(n%i == 0)
{
for(int j = 1; j*i <= m; j++)
flag[j*i] = 1;
ret -= ret/i;
while(n%i == 0)
n /= i;
}
}
if(n > 1)
{
for(int j = 1; j*n <= m; j++)
flag[j*n] = 1;
ret -= ret/n;
}
return ret;
}
int main()
{
while(~scanf("%d %d",&n,&k))
{
int cnt = Eular(n),t;
t = k/cnt;
if(k%cnt == 0)
t--;
kk = k - t*cnt;
int cou = 0,i;
for(i = 1; i <= n; i++)
{
if(flag[i] == 0)
cou++;
if(cou == kk)
break;
}
printf("%d\n",i+t*n);
}
return 0;
}