首页 > 代码库 > hdu 1576 求逆元

hdu 1576 求逆元

2024-07-30 21:57:36   221人阅读

题意：给出n=A mod 9973和B，求(A/B) mod 9973

 

昨天用扩展欧几里得做过这题，其实用逆元也可以做。

逆元的定义：例如a*b≡1 (mod m)，则b就是a关于m的逆元。

求逆元方法也很简单，用扩展欧几里得解这个方程即可。

逆元性质：若a是b的逆元，则(x/a)mod p=(x*b)mod p

 

对于本题呢？设B的逆元为x，

那么有(A/B) mod 9973=((A mod 9973)*(x mod 9973))mod 9973

 

Reference:  http://blog.csdn.net/leonharetd/article/details/13095191

 1 #include <iostream> 2 using namespace std; 3 __int64 a,b,b1,x,k,tm,r,T,n,ans; 4  5 __int64 extend_gcd(__int64 a,__int64 b,__int64 &x,__int64 &y) 6 { 7     if (b==0) 8     { 9         x=1;10         y=0;11         return a;12     }13     else14     {15         __int64 r=extend_gcd(b,a%b,y,x);16         y=y-x*(a/b);17         return r;18     }19 }20 21 int gcd(int a,int b)22 {23     if (b==0) return a;24     return gcd(b,a%b);25 }26 27 int main()28 {29     cin>>T;30     while (T--)31     {32         cin>>n>>b;33         //bx==1 (mod m)34         tm=extend_gcd(b,9973,x,k);35         b1=x*(1/tm);36         r=9973/tm;37         b1=(b1%r+r)%r;    //求出最小非负整数解38         ans=(n*(b1%9973))%9973;39         cout<<ans<<endl;40 41     }42     return 0;43 }

 

hdu 1576 求逆元


联系
我们