Happy 2006 POJ - 2773

题目链接：

题目：

如果大公约数（GCD）为1，则两个正整数被认为是相对素数。例如，1,3,5,7,9 ......都是相对于2006年的素数。

现在你的工作很简单：对于给定的整数m，当这些元素按升序排序时，找到相对于m的相对素数的第K个元素。

输入

输入包含多个测试用例。对于每个测试用例，它包含两个整数m（1 <= m <= 1000000），K（1 <= K <= 100000000）。

产量

在单行中输出第K个元素。

Sample Input

2006 12006 22006 3

Sample Output

135 思路：由欧几里得算法得知：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 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include
            
             #include
             using namespace std;typedef long long ll;const int maxn=3e6+7;int a[maxn];#define MAX 0x3f3f3f3fint 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;}