// 题意 :给你两个数 m(10^6),k(10^8) 求第k个和m互质的数是什么
这题主要需要知道这样的结论
gcd(x,n)=1 <==> gcd(x+n,n)=1
证明 假设 gcd(x,n)=1 gcd(x+n,n)!=1
令 a=n+x b=n 设 gcd(a,b)=k>1
那么有 a=Ak b=Bk x+Bk=Ak => x=(A-B)k
k是n的因子 那么 x=(A-B)k 显然不成立 因为x不可能含有因子k(因为x,n互质);
所以假设不成立
那么这题剩下的就算求 比m小 与m互质的数就可以了
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <string.h>
using namespace std;
#define maxm 100010
#define maxn 1000110
int prim[1010],p;
bool f[maxn];
int ans[maxn],rp[1010];
void getprime(){
int i,j;
for(i=4;i<=1000;i+=2)
prim[i]=1;
for(i=3;i*i<=1000;i+=3)
if(!prim[i])
for(j=i*i;j<=1000;j+=i)
prim[j]=1;
for(i=2;i<=1000;i++)
if(!prim[i]) prim[p++]=i;//,printf("%d ",i);
}
int main()
{
getprime();
int m,k;
while(scanf("%d %d",&m,&k)!=EOF){
int i=0,j,n=m,num=0;
while(i<p){ //分解
if(n%prim[i]==0){
rp[num++]=prim[i];
while(n%prim[i]==0) n=n/prim[i];
}
if(n==1) break;
i++;
}
if(n!=1) rp[num++]=n;
for(i=1;i<=m;i++)
f[i]=0;
for(i=0;i<num;i++)//筛选删除
for(j=rp[i];j<=m;j+=rp[i])
f[j]=1;
num=0;
for(i=1;i<=m;i++) // 其实这里面的num可以用容斥原理算 估计会快在常数上
if(!f[i]) ans[num++]=i;
printf("%d
",ans[(k-1)%num]+(k-1)/num*m);
}
return 0;
}