Description The modular modular multiplicative inverse of an integer a modulo m is an integer x such that a-1≡x (mod m). This is equivalent toax≡1 (mod m). Input There are multiple test cases. The first line of input is an integer T ≈ 2000 indicating the number of test cases. Each test case contains two integers 0 < a ≤ 1000 and 0 < m ≤ 1000. Output For each test case, output the smallest positive x. If such x doesn't exist, output "Not Exist". Sample Input 3 3 11 4 12 5 13 Sample Output 4 Not Exist 8   题目大意：求a关于模m的逆。 解题思路：1>扩展欧几里得算法：找出一对整数对（x,y),使得ax+by=gcd(a,b). 　　　　　2>设a,b,c为任意整数.若方程ax+by=c的一组整数解为(x,y)，则它的任意解为（x+k*b',y+k*a'),其中a'=a/gcd(a,b),b'=b/gcd(a,b),k任意整数. 　　　　　3>模线性方程：输入正整数：a,b,n，解方程ax≡b(mod n)即：a-b是n的整数倍即：ax-b=ny.          4>ax≡1 (mod m)等价于：ax%m==1%m 也等价于：ax-my=1是否有整数解且求出满足条件的最小整数x。扩展欧几里得算法1必须是gcd(a,m)的倍数，所以a和n互素即：gcd(a,m)=1才会有解，在该条件下有唯一解。   1 #include 2 #include<string.h> 3 #include 4 #include<string> 5 using namespace std; 6 void gcd(int a,int b,int& d,int& x,int& y){ 7 if(!b){ 8 d=a;x=1;y=0; 9 }else{ 10 gcd(b,a%b,d,y,x); 11 y-=x*(a/b); 12 } 13 }//扩展欧几里得算法，a,b,是输入量 14 //d为gcd(a,b),x,y为ax+by=gcd(a,b)的一组整数解 15 int main(){ 16 int T;cin>>T; 17 while(T--){ 18 int a,m,d,x,y; 19 cin>>a>>m; 20 gcd(a,m,d,x,y); 21 if(d!=1)cout<<"Not Exist "; 22 else{//根据一组解求满足条件的x 23 if(x>0){ 24 while(x>0)x-=m; 25 x+=m; 26 }else if(x<0){ 27 while(x<0)x+=m; 28 }else x+=m; 29 cout<' '; 30 } 31 }return 0; 32 }