题目地址：http://poj.org/problem?id=2773

因为k可能大于m,利用gcd(m+k,m)=gcd(k,m)=gcd(m,k)的性质,最后可以转化为计算在[1,m]范围内的个数t。

1、AC代码：

开始的时候从1开始枚举if(gcd(n,i)==1)，果断跑了2000ms

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cstring>

#include <string>

#include <vector>

#include <list>

#include <deque>

#include <queue>

#include <iterator>

#include <stack>

#include <map>

#include <set>

#include <algorithm>

#include <cctype>

#include <cfloat>

using namespace std;

typedef __int64 LL;

const int N=1000002;

const LL II=1000000007;

const int INF=0x3f3f3f3f;

const double PI=acos(-1.0);

inline int in()

{

    char ch = getchar();

    int data = 0;

    while (ch < '0' || ch > '9')

    {

        ch = getchar();

    }

    do

    {

        data=data*10+ch-'0';

        ch=getchar();

    }while(ch>='0'&&ch<='9');

    return data;

}

int xh[N];

int gcd(int n,int m)

{

    int t;

    while(m)

    {

        t=n%m;

        n=m;

        m=t;

    }

    return n;

}

int main()

{

    int i,j,n,k;

    xh[1]=1;

    while(cin>>n>>k)

    {

        if(n==1)

        {

            printf("%d\n",k);

            continue;

        }

        int x=1;

        for(i=2;i<n;i++)

        {

            if(gcd(n,i)==1)

                xh[++x]=i;

        }

        int t=k%x,p=(k-1)/x;

        if(t==0)

            t=x;

        printf("%d\n",p*n+xh[t]);

    }

    return 0;

}

2、AC代码

将于m互质的数记录下来。

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cstring>

#include <string>

#include <vector>

#include <list>

#include <deque>

#include <queue>

#include <iterator>

#include <stack>

#include <map>

#include <set>

#include <algorithm>

#include <cctype>

#include <cfloat>

using namespace std;

typedef __int64 LL;

const int N=1000002;

const LL II=1000000007;

const int INF=0x3f3f3f3f;

const double PI=acos(-1.0);

inline int in()

{

    char ch = getchar();

    int data = 0;

    while (ch < '0' || ch > '9')

    {

        ch = getchar();

    }

    do

    {

        data=data*10+ch-'0';

        ch=getchar();

    }while(ch>='0'&&ch<='9');

    return data;

}

int xh[N];

LL pri[N],x;

bool vis[N];

void prime()//求素数

{

    LL i,j;

    x=0;

    memset(vis,false,sizeof(vis));

    for(i=2;i<N;i++)

    {

        if(!vis[i])

            pri[++x]=i;

        for(j=1;j<=x&&pri[j]*i<N;j++)

        {

            vis[pri[j]*i]=true;

            if(i%pri[j]==0)

                break;

        }

    }

}

int main()

{

    LL n,k,i,j;

    prime();

    while(scanf("%I64d%I64d",&n,&k)!=EOF)

    {

        LL q=n,sum=n;

        if(n==1)

        {

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

            continue;

        }

        memset(xh,0,sizeof(xh));

        for(i=1;i<=x&&pri[i]*pri[i]<=n;i++)

        {

            if(n%pri[i]==0)

            {

                sum=sum*(pri[i]-1)/pri[i];

                for(j=1;j*pri[i]<=q;j++)

                    xh[pri[i]*j]=1;//这个地方和上面的可能越界，所以要用__int64

            }

            while(n%pri[i]==0)

            {

                n/=pri[i];

            }

        }

        if(n>1)

        {

            sum=sum*(n-1)/n;

            for(j=1;j*n<=q;j++)

                xh[j*n]=1;

        }

        //sum m以内与m互素的个数

        LL t=k%sum,p=k/sum;

        if(t==0)

        {

            t=sum;

            p--;

        }

        LL temp=0;

        for(i=1;i<=q;i++)

        {

            if(xh[i]==0)

                temp++;

            if(temp==t)

            {

                printf("%I64d\n",p*q+i);

                break;

            }

        }

    }

    return 0;

}