题意:输入两个数m,k。求与m互素的第k个数。
题解:我们知道,如果a和m互素,那么k*m+a与m互素。也就是说【1,m-1】,与【k*m+1,k*m+m-1】区间存在一个对应关系:【1,m-1】中与m互素的个数 = 【k*m+1,k*m+m-1】中与m互素的个数。
另外,值得注意的是,我们在求欧拉函数的过程中实际上求出了m所有的素因子,既然如此,就可以通过筛选法筛掉所有与m不互素的数。
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<ctime> #include<algorithm> using namespace std; bool pri[1000009]; int Euler ( int n ) { int i, j, m = n, ret = n; memset(pri,0,n+1); for ( i = 2; i * i <= n; i++ ) { if ( n % i == 0 ) { n /= i; for ( j = 1; i * j <= m; j++ ) //用筛选法标记所有与n不互素的数 pri[i*j] = 1; ret = ret - ret / i; while ( n % i == 0 ) n = n / i; } } if ( n > 1 ) // 当n>1的时候,n本身也是一个素因子 { for ( j = 1; n * j <= m; j++ ) pri[n*j] = 1; ret = ret - ret / n; } return ret; } int main() { int m, k; while ( scanf("%d%d",&m, &k) != EOF ) { int p = Euler(m); int tmp = k / p; if ( k % p == 0 ) tmp--; k = k - p * tmp; int i, cnt = 0; for ( i = 1; i <= m; i++ ) { if ( ! pri[i] ) cnt++; if ( cnt == k ) break; } printf("%d\n",i+m*tmp); } return 0; }