思路:
把k*M%N=1可以写成一个不定方程,(k*M)%N=(N*x+1)%N,那么就是求k*M-N*x=1,k最小,不定方程我们可以直接利用exgcd,中间还搞错了; //小小地讲一下exgcd球不定方程原理 对于ax+by=gcd(a,b); 我们设一下a>b,在简单直接把b=0时,gcd(a,b)=a.此时,x=1,y=0; 接着,a>b>0,我们这里可以摆两个式子:①:ax1+by1=gcd(a,b);继续,②:bx2+(a mod b)y2=gcd( b , a mod b );第二个式子为何呢?这就是gcd的辗转相除法的算法啊。而且gcd(a,b)=gcd(b,a mod b); 然后我们就能将gcd左边两个等式列个等式:ax1+by1=bx2+(a mod b)y2;额。。。a mod b可以写成?a-(a/b)b对吧,那么等式变成ax1+ by1= bx2+ (a - (a / b) * b)y2=bx2+ay2 - (a / b)by2 ;我们把ax1+ by1=bx2+ay2 - (a / b)by2拎出来,整理一下,写成:ax1+by1=ay2+b(x2-(a/b)y2); 那么很明显我们可以得到,x1=y2,y1=x2-(a/b)y2; 这样我们就得到了求解 x1,y1 的方法:x1,y1 的值基于 x2,y2.#includeusing namespace std;typedef long long LL;const int N=1e4;void exgcd(LL &k,LL &x,LL a,LL b){ if(b==0) { k=1; x=0; return; } exgcd(k,x,b,a%b); LL temp=k; k=x; x=temp-(a/b)*x;}int main(){ LL n,m; LL k,x; scanf("%lld%lld",&m,&n); exgcd(k,x,m,n); while(k<0) k=(k+n)%n; printf("%lld\n",k); return 0;}