n=A%9973 A/B%9973=x
A/B=x+9973k
A=Bx+9973Bk
則 n=Bx%9973 gcd(B,9973) = 1
Bx=n+9973y
Bx+(-9973y)=n(不定方程)
Bx≡n(mod 9973)(同余式)
#include <iostream> #define mod 9973 using namespace std; int ex_gcd(int a,int b,int &x,int &y) {if(!b){x=1,y=0;return a;}int r=ex_gcd(b,a%b,x,y);int t=x;x=y;y=t-a/b*y;return r; } int main() {int b,n,x,y;int t;cin>>t;while(t--){cin>>n>>b;int d=ex_gcd(b,mod,x,y);//在這兒d確定為1了x*=n;cout<<(x%mod+mod)%mod<<endl;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的hdu 1576的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。