Happy 2006 POJ - 2773(欧几里得算法 互素问题)

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

 


Happy 2006 POJ - 2773(欧几里得算法 互素问题)

上一篇:Python的内置方法


下一篇:【spring-boot】Could not find result map 'com.springboot.cib_hk.bean.Users' referenced from 'com.springboot.cib_hk.mapper.UsersMapper.selectByUsername'