poj2773求第K个与m互质的数

//半年前做的，如今回顾一下，还是有所收货的，数的唯一分解,.简单题。

#include<iostream>

#include<cstring>

using namespace std;

int a[1000001];int p[1000000];   //用a来筛去m的唯一分解后的质因子及其倍数,流下就是与其互质的数。

int main()

{

    int m,k;

    while(cin>>m>>k)

    {

        memset(a,0,sizeof(a));

        memset(p,0,sizeof(p));

        int mm=m;

        for(int i=2;i<=mm;i++)     //此处mm即可

         {

             if(mm%i==0)

             {

                for(int j=i;j<=m;j+=i)  //筛去

                  a[j]=1;

                while(mm%i==0)mm/=i;    //除掉

             }

         }

         int t=1;      //t记录有多少个，

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

         {

             if(a[i]==0)p[t++]=i;        //p[i]记录第i个互质数（1--m）

         }

         t--;                           //1--m内有t个，那么m--2m,2m--3m....必然也有t个！每层相差m。

         if(k%t==0)cout<<p[t]+m*(k/t-1)<<endl;//考虑特殊位子。

         else cout<<m*(k/t)+p[k%t]<<endl;

    }

    return 0;

}

巴特西

poj2773求第K个与m互质的数

最新文章

热门文章