首页 > 代码库 > HDU - 1576 A/B(扩展欧几里得算法)

HDU - 1576 A/B(扩展欧几里得算法)

2024-09-24 18:24:39   204人阅读

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1576

题意：要求(A/B)%9973，但由于A很大，我们只给出n(n=A%9973)(我们给定的A必能被B整除，且gcd(B,9973) = 1)。

普通版欧几里得算法（辗转相除）：

1 typedef long long LL;2 LL gcd(LL a,LL b){3     return (b==0) ? a : gcd(b,a%b);4 }

扩展欧几里得算法（理论）：对于不完全为0的非负整数，a，b，gcd（a，b）表示a，b的最大公约数，必然存在整数对x，y使得 gcd（a，b）=ax+by

1 LL e_gcd(LL a,LL b,LL &x,LL &y){2     LL d=a;3     if(b!=0){4         d=e_gcd(b,a%b,y,x);5         y-=(a/b)*x;6     }    7     else {x=1;y=0;}8     return d;9 }//扩展欧几里得算法a*x+b*y=gcd；既可以求出x,y，顺便把gcd也求出来了

1.题目思路（别人家的 (￣.￣)+）：

设(A/B)%9973 = k, 则A/B = k + 9973x  (x未知）， 因此A = kB + 9973xB,

又A%9973 = n（n是已知条件），所以kB%9973 = n,  故kB = n + 9973y (y未知)

故(k/n)B +(-y/n)*9973 = gcd(B,9973) = 1（公式中只有k，y不知道）

扩展欧几里得 求出k/n,  再乘以个n，记得取模，就是answer了

 1 #include <iostream>       2 using namespace std; 3  4 typedef long long LL; 5 const int MOD=9973; 6  7 LL e_gcd(LL a,LL b,LL &x,LL &y){ 8     LL d=a; 9     if(b!=0){10         d=e_gcd(b,a%b,y,x);11         y-=(a/b)*x;12     }    13     else{x=1;y=0;}14     return d;15 }16    17 int main(){    18     LL n,b,t,x,y;    19     cin>>t;       20     while(t--){    21         cin>>n>>b;    22         e_gcd(b,MOD,x,y);    23         x=(x%MOD+MOD)%MOD;    24         cout<<(x*n)%MOD<<endl;25     }    26     return 0;    27 }

 

HDU - 1576 A/B(扩展欧几里得算法)


联系
我们