题意:给出一个数m,让我们找到第k个与m互质的数。
方法:这题有两种方法,一种是欧拉函数+容斥原理,但代码量较大,另一种办法是欧几里德算法,比较容易理解,但是效率很低。
我这里使用欧几里德算法,欧几里德算法又名辗转相除法,原先单纯的用于求最大公约数,这里也算是一个小小的拓展应用,这个题利用的欧几里德算法的重要性质,假如a与b互质,那么b*t+a与b也一定互质,那样我们可以枚举1~m之间所有符合条件的数,然后打一个表格,求出所有符合条件的数,正如下表中的(5,5)所示,这个表格是一个带有周期性的自上而下的规律表格,有了这个规律,打完表以后就可以很快的求出答案来了。
5 5
Pri[1] = 1 6 11 16...
Pri[2] = 2 7 12 17...
Pri[3] = 3 8 13 18...
Pri[4] = 4 9 14 19...
6
代码如下:
#include<iostream>
#include<cstdio>
using namespace std;
int pri[];
int gcd ( int a, int b )
{
return b == ? a : gcd ( b, a % b ) ;
}
int main()
{
int m, k ;
while (~scanf("%d%d",&m,&k))
{
int i, j ;
for (i = , j = ; i <= m ; i ++ )
{
if ( gcd ( m, i ) == )
{
pri [ j ++ ] = i ;
/*printf("Pri[%d] = %d ",j-1,i);
for(int k = 1; k <= 3; k++)
{
printf(" %d",k*m+i);
}
printf("...\n");*/
}
}
j--;
if(k%j == ) printf("%d\n",(k/j-)*m + pri[j]);
else printf("%d\n",k/j*m + pri[k%j]);
}
return ;
}