Happy 2006 POJ - 2773
题目链接：https://vjudge.net/problem/POJ-2773#author=0
题目：
如果大公约数（GCD）为1，则两个正整数被认为是相对素数。例如，1,3,5,7,9 ......都是相对于2006年的素数。
现在你的工作很简单：对于给定的整数m，当这些元素按升序排序时，找到相对于m的相对素数的第K个元素。
输入
输入包含多个测试用例。 对于每个测试用例，它包含两个整数m（1 <= m <= 1000000），K（1 <= K <= 100000000）。
产量
在单行中输出第K个元素。
Sample Input
2006 1 2006 2 2006 3Sample Output
1 3 5
思路：由欧几里得算法得知：gcd(a,b)=gcd(a+b*t,b),故当k超过m时，后面的数与前面1~m中与m互质的数具有周期性，
即1~m中与m互质的数，加上m就是m~2m与m互质的数，所以只要求出1~m与m互质的数即可
// // Created by hanyu on 2019/8/9. // #include <algorithm> #include <iostream> #include <cstdio> #include <cstring> #include <queue> #include <set> #include<math.h> #include<map> using namespace std; typedef long long ll; const int maxn=3e6+7; int a[maxn]; #define MAX 0x3f3f3f3f int Gcd(int x,int y) { if(y==0) return x; else return Gcd(y,x%y); } int main() { int m,k; while(~scanf("%d%d",&m,&k)) { int pos=0; for(int i=1;i<=m;i++) { if(Gcd(i,m)==1) a[++pos]=i; }//1~m中所有与m互质的数，共有pos个 int num; int t=k/pos;//看是否满足一整个周期 int t1=k%pos;//在每个周期中的位置 if(t1==0)//整除则说明是一个周期中最后一个与m互质的数 num=(t-1)*m+a[pos];//每个周期中的每个数都要加m，故周期数-1乘m else num=t*m+a[t1]; printf("%d\n",num); } return 0; }