求逆元 HDU1576

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 
 5 using namespace std;
 6 
 7 int exgcd(int a,int b,int &x,int &y)
 8 {
 9     if(b==0)
10     {
11         x=1;
12         y=0;
13         return a;
14     }
15     int ret=exgcd(b,a%b,x,y);
16     int tmp=x;
17     x=y;
18     y=tmp-a/b*y;
19     return ret;
20 }
21 
22 int main()
23 {
24     int t;
25     cin>>t;
26     while(t--)
27     {
28         long long n,b;
29         cin>>n>>b;
30         int bb,xx;
31         exgcd(b,9973,bb,xx);  
32         bb=bb%9973+9973;
33         cout<<n*bb%9973<<endl;
34     }
35     return 0;
36 }

View Code

•若m≥1，（a，m）＝1，则存在c使得
ca≡1（mod m）
我们把c称为是a对模m的逆，记为
a逆（mod m）或a逆
可以用扩展欧几里德算法求a－1

•应用：
求(a/b)%c时，若a为大整数时可以写成
（(a%c)*b逆）%c