// 题意 ：给你两个数 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#include #include #include #include #include #include using namespace std;#define maxm 100010#define maxn 1000110int 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