算法是关键，得出1-m内的互质数，然后类推计算即可。下面有详细说明。
#include#include 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<