POJ-2773 Happy 2006，暴力2700ms+水过！

Happy 2006

这个题很可能会超时的，但我几乎暴力的方法2700ms+过了，可能是后台水吧。开始没有什么思路，如果k小的话或许直接暴力可以，但k会比m都大，于是超过m的就不造怎么求了。。。看了讨论区某位大神的留言突然发现如果gcd(a,m)=1，那么gcd(a+km,m)=1也成立，这个用广义欧几里德即辗转相除法原理就可以明白了。

题意：就一句话，给定两个正整数m,k；求m的第k个互质数。

思路：我们可以发现小于m并且与m互质的数就构成了一个模m的简化剩余系，个数就是euler(m)，那么这些数每个都加上m又会构成另一个简化剩余系。于是求第k个只需知道m的最小简化剩余系然后再加上m的倍数即可。

首先要把与m互质的数筛出来，那么就是1e6log(1e6)，开始是想把素数先打个表看看能否优化些时间，后来把这部分去了，直接求一个数的简化剩余系也过了2922MS，好有趣。优化了一下又交了几发2782MS。注意1
1这组数据，开始还re了两发。

const int N=1e6+10;

ll m,k,a[N];

void init(ll *a,int &len)//把小于m并且与m互质的数筛出来；

{

    for(ll i=1; i<=m; i++)

        int len=0;

    if(__gcd(i,m)==1) a[++len]=i;

}

ll find()

{

    if(x==0) return a[len]+(k-1)*m;

    init(a,len);//len是个数；

    ll x=k%len;

    k/=len;

    return a[x]+k*m;

}

int main()

{

    while(~scanf("%I64d%I64d",&m,&k))//注意1 1这组数据

    {

        printf("%I64d\n",find());

    }

    return 0;

}

这里提到的简化剩余系在信安数学基础里的含义是：简化剩余系。

巴特西

POJ-2773 Happy 2006，暴力2700ms+水过！

最新文章

热门文章