|
A/BTime Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
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
题解:
因为:题目已知n和B,又知gcd(B,9973) = 1,
且n=A%9973,需要求(A/B)%9973,
由于不知道A,所以需要把A替换掉,
所以设
ans=(A/B)%9973 ……
(1) (1)式中 存在x使得
A/B=9973x+ans, …… (2)
(2) 式中两边同时乘上B,得
A=9973*B*x+ans*B
…… (3) 又因n=A%9973,
一定存在y使得
n=A-9973*y …… (4)
把(3)代入(4)得
n=9973*B*x+ans*B -9973*y
合并得
n=ans*B +(B*x-y)9973 …… (5)
又有 gcd(B,9973) = 1,所以(5)式两边同时除以n,得
1=ans/n*B+(B*x-y)/n*9973
就可以看成ax+by=1的形式,
运用扩展的欧几里德算法求出ans/n,
此时a=B,b=9973,x=ans/n;
所以套用扩展的欧几里德算法模版求出x,然后再乘上n,即可得出结果ans=(A/B)%9973;
代码实现:
#include<iostream> using namespace std; const int MOD=9973; void extendGcd(int a,int b,int &x,int &y) //扩展gcd,可以求出gcd(a,b)以及ax+by=gcd(a,b)中x,y的值 { if(b==0) { x=1; y=0; return; } else { extendGcd(b,a%b,x,y); int tmp=x; x=y; y=tmp-a/b*y; } } int main() { int t,n,b,x,y,tmp; cin>>t; while(t--) { cin>>n>>b; extendGcd(b,MOD,x,y); //解出bx+9973y=1的x x*=n; //此时的x为 n=ans*B +(B*x-y)9973 中的解ans了 tmp=(x%MOD+MOD)%MOD; //防止x为负,有题意x必为正数 cout<<tmp<<endl; } return 0; } |