比赛的时候卡在这里，都是我没有把题目看懂，m=1的情况没考虑好，直接当不存在处理了==
下面给一种暴力法
不过时间也是很快的
#include<iostream>
#include<cstdio>
using namespace std;
int t;
int main()
{
int t,a,m,aa,ans,mm,i;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&a,&m);
if(m==1||a==1)
{
printf("1\n");
continue;
}
if(a%m==0||m%a==0)
{
printf("Not Exist\n");
continue;
}
for(i=1;i<m;i++)
{
if(a*i%m==1)
{
break;
}
}
if(i==m)
{
printf("Not Exist\n");
}
else
{
printf("%d\n",i);
}
}
return 0;
}
下面是我比赛时想的，因为m=1考虑出错，结果很悲剧
#include<iostream>#include<cstdio>
using namespace std;
int run(int a,int b)
{
if(a<b)
{
a^=b;
b^=a;
a^=b;
}
if(b==0) return a;
return run(b,a%b);
}
int t;
int main()
{
int t,a,m,aa,ans,mm;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&a,&m);
if(m==1||a==1)
{
printf("1\n");
continue;
}
if(a%m==0||m%a==0)
{
printf("Not Exist\n");
continue;
}
if(run(a,m)==1)
{
if(a>m)
{
aa=a;
while(aa%m!=1)
{
aa+=a;
}
ans=aa/a;
}
else
{
mm=m;
while((mm+1)%a!=0)
{
mm+=m;
}
ans=(mm+1)/a;
}
printf("%d\n",ans);
}
else
{
printf("Not Exist\n");
}
}
return 0;
}