happy 2006，欧几里得算法（gcd）及扩展

欧几里得算法

欧几里得算法是用来求最大公约数的算法，简称GCD
再次借用一下鹏哥的笔记。

由欧几里得算法可得：
Gcd(a,b）=Gcd（b%a，a）

以上内容看不懂就不用纠结了，记住下面的代码就好了。
代码实现：

int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}

扩展欧几里得

给出不定方程 ax+by=Gcd(a,b)，拓展欧几里得算法可用于求解不定方程组的整数根（x,y).

![/**
    求解满足ax+by=Gcd(a,b)的所有解(x,y)
*/
int extendGcd(int a,int b,int &x,int &y)
{
    if(a == 0)
    {
        x=0,y=1;
        return b;
    }

    int gcd=extendGcd(b%a,a,x,y);
    int x2=x,y2=y;
    y=x2;
    x=y2-b/a*x2;
	//可简写为
	//int gcd=extendGcd(b%a,a,y,x);
	//x -= b/a*y;

    return gcd;
}

例题Happy 2006

Two positive integers are said to be relatively prime to each other if the Great Common Divisor (GCD) is 1. For instance, 1, 3, 5, 7, 9…are all relatively prime to 2006.

Now your job is easy: for the given integer m, find the K-th element which is relatively prime to m when these elements are sorted in ascending order.

Input

The input contains multiple test cases. For each test case, it contains two integers m (1 <= m <= 1000000), K (1 <= K <= 100000000).

Output

Output the K-th element in a single line.

Sample Input

2006 1
2006 2
2006 3

Sample Output

1
3
5

题目大意，要找出从1开始，与m互素的第k个数。互素即Gcd（m,x）=1既称m与x互素。
一开始的想法肯定是一一枚举，但很显然会tle，所以便需要应用到欧几里得gcd(a,b)=gcd(a+b*t,b)，枚举小于m的所有互素的数，然后这些数加上一个m也与m互素
我们可以把它看成一定的周期性。
所以对于小于m且与m互素的我们可以用gcd找出来，并存入数组，而对于大于k的，我们可以利用这种周期性。

//cont为小于m且与m互素的个数，repr为存入这些数的数组。
        if(k%cont==0)
        cout<<(k/cont-1)*m+repr[cont-1]<<endl;
        else
        cout<<(k/cont)*m+repr[k%cont-1]<<endl;

AC代码

#include<iostream>
#include<stdlib.h>
#include<string.h>
using namespace std;
int repr[1000001];
int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}
int main()
{
    int  m,k;
    while(scanf("%d%d",&m,&k)!=EOF)
    {
        memset(repr,0,sizeof(repr));
        int cont=0;
        int i;
        for( i=1;i<=m;i++)
        {
            if(gcd(m,i)==1)
            {
                repr[cont]=i;
                cont++;
            }
        }
        //cout<<repr[k];
        if(k%cont==0)
        cout<<(k/cont-1)*m+repr[cont-1]<<endl;
        else
        cout<<(k/cont)*m+repr[k%cont-1]<<endl;
    }
    return 0;
}