<题目链接>
<转载于 >>> >
A/B
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)。
每组数据有两个数n(0 <= n < 9973)和B(1 <= B <= 10^9)。
Output
对应每组数据输出(A/B)%9973。
Sample Input
2
1000 53
87 123456789
Sample Output
7922
6060
解题分析：
设(A/B)%9973 = K, 则A/B = k + 9973x (x未知）， 因此A = kB + 9973xB,
又A%9973 = n， 所以kB%9973 = n, 故kB = n + 9973y (y未知)
故(k/n)B +(-y/n)*9973 = gcd(B,9973) = 1 ***注意这里相当于利用扩展欧几里得求逆元，所以要注意只有当a与b互质的时候才能够用欧几里得求逆元，即这里的gcd(B,9973)=1
根据扩展欧几里得求出x(也就是方程中的k/n), 再乘以个n，再取模。
#include <cstdio> #define m 9973 void extend_gcd(int a,int b,int &x,int &y) //扩展欧几里得模板
{
if(b==)
{
x=,y=;
return ;
}
extend_gcd(b,a%b,x,y);
int r=x;
x=y;
y=r-(a/b)*y;
} int main()
{
int n,b,t,x,y;
scanf("%d",&t); while(t--)
{
scanf("%d%d",&n,&b);
extend_gcd(b,m,x,y); //x=k/n(k为答案)
x=(x%m+m)%m;
printf("%d\n",(x*n)%m);
}
return ;
}
2018-07-30