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

題解：設 A % 9973 = r1;則 A = k * 9973 + r1 ；

? 令C = A/B , C % 9973 = r2，C = 9973 * x + r2；

所以可列出等式：k*9973 + r1 = 9973 * x * B + r2 * B；

兩邊同時對9973取模可得：r2 * B = r1 （mod 9973）；

r2*B + 9973 * y = r1；

運用擴展歐幾里得求解r2，對r2處理得正數，r1*r2%9973即為所求答案；

#include <iostream> #include <cstdio> using namespace std; __int64 x,y; void edgcd(__int64 a,__int64 b) {if(b == 0){x = 1;y = 0;}else{gcd(b,a%b);__int64 temp = x;x = y;y = temp - a/b*y;} } int main() {int n;__int64 a,b;scanf("%d",&n);while(n--){scanf("%I64d%I64d",&a,&b);edgcd(b,9973);while(x<0)x=(x+9973)%9973;printf("%I64d\n",x*a%9973);}return 0; }

總結

以上是生活随笔為你收集整理的hdu-1576（A/B）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。