POJ 2773 互素问题

题目大意就是给出n和k求出第k个与n互素的数

如果知道欧几里德算法的话就应该知道gcd（b×t+a，b）=gcd（a，b） （t为任意整数）

则如果a与b互素，则b×t+a与b也一定互素，如果a与b不互素，则b×t+a与b也一定不互素

故与m互素的数对m取模具有周期性，则根据这个方法我们就可以很快的求出第k个与m互素的数

假设小于m的数且与m互素的数有k个，其中第i个是ai，则第m×k+i与m互素的数是k×m+ai

这道题这样做并不是最优的，网上说可以用欧拉函数+容斥原理+二分枚举可做，我暂时还不知道这样做的思想

如果用我的方法做的话，时间上的花费比较大

poj2773 Happy 2006view raw

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
usingnamespace std;
int pri[1000000];
int gcd ( int a , int b ) 
{
    return b ==0? a : gcd ( b , a % b ) ;
}
int main()
{
    int m , k ;
    while ( cin >> m >> k ) 
    {
        int i , j ;
        for ( i =1 , j =0 ; i <= m ; i ++ )
            if ( gcd ( m , i ) ==1 )
                pri [ j ++ ] = i ;

        if ( k%j !=0)
            cout <<k/j * m +pri[k%j-1] << endl;
        else//要特别考虑k%j=0的情况，因为数组是从0开始的，第i个对应的是pri[i-1]
            cout << (k/j-1)*m+pri[j-1] << endl ;
    }
    return0;
}