hdu 1576 AB

Problem Description 要求(A/B)%9973，但由于A很大，我们只给出n(n=A%9973)(我们给定的A必能被B整除，且gcd(B,9973) = 1)。   Input 数据的第一行是一个T，表示有T组数据。 每组数据有两个数n(0 <= n < 9973)和B(1 <= B <= 10^9)。   Output 对应每组数据输出(A/B)%9973。   Sample Input 2 1000 53 87 123456789   Sample Output 7922 6060

扩展欧几里得：

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

A%9973==n，所以 KB%9973==n；

故(K/n)B +(-y/n)*9973 = gcd(B,9973) ;

转化为 ax+by=gcd（a，b）；

所以直接用扩展欧几里得求出x==K/n;

再让x*n即为所求；

#include<stdio.h> #include<iostream> #include<algorithm> #include<math.h> #include<string.h> using namespace std; int exgcd(int a,int b,int &x,int &y) { if(b==0) { x=1; y=0; return a; } int r=exgcd(b,a%b,x,y); int t=x; x=y; y=t-a/b*y; return r; } int main() { int n,b,ans,x,y; int T; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&b); exgcd(b,9973,x,y); x=(x+9973)%9973; printf("%d\n",(x*n)%9973); } }