因為k可能大於m,利用gcd(m+k,m)=gcd(k,m)=gcd(m,k)的性質,最後可以轉化為計算在[1,m]范圍內的個數t。
1、AC代碼：
開始的時候從1開始枚舉if(gcd(n,i)==1)，果斷跑了2000ms
[cpp]
#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;
}
#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互質的數記錄下來。
[cpp]
#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;
}
#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;
}
