hdu 1576

本文主要是介绍hdu 1576，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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;
}

这篇关于hdu 1576的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---