Happy 2006 POJ - 2773（欧几里得算法互素问题）

逃离我推掉我的手 2023-08-17 15:40 65阅读 0赞

# Happy 2006 POJ - 2773 #

题目链接：[https://vjudge.net/problem/POJ-2773\#author=0][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 3

Sample 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;
    }

转载于:https://www.cnblogs.com/Vampire6/p/11329663.html

[https_vjudge.net_problem_POJ-2773_author_0]: https://vjudge.net/problem/POJ-2773#author=0