首页 > 代码库 > hdu 1576 扩展欧几里得
hdu 1576 扩展欧几里得
(A/B)%9973=K
A/B=K+9973*X
A=BK+9973*X*B
A%9973=n;
BK%9973=n;
BK=n+9973*Y
(K/n)*B+(-Y/n)*9973=GCD(B,9973)=1;
求出k/n,求出k
1 /* 2 扩展欧几里得 3 扩展欧几里德算法是用来在已知a, b求解一组x,y使得ax+by = Gcd(a, b) =d(解一定存在,根据数论中的相关定理) 4 */ 5 #include<cstdio> 6 #include<iostream> 7 #define ll long long 8 9 using namespace std; 10 11 ll x,y; 12 void gcd(ll a,ll b) 13 { 14 if(b==0) 15 { 16 x = 1; 17 y = 0; 18 return ; 19 } 20 gcd(b,a%b); 21 ll t = x; 22 x = y; 23 y = t-(a/b)*y; 24 } 25 int main() 26 { 27 int t; 28 int n,b; 29 cin>>t; 30 while(t--) 31 { 32 cin>>n>>b; 33 gcd(b,9973); 34 //x*=n; 35 x = (x%9973+9973)%9973; //最小正数 36 cout<<(x*n)%9973<<endl; 37 } 38 return 0; 39 }
hdu 1576 扩展欧几里得
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。