nyoj1235 A/B Problem(扩展欧几里德求逆元)

nyoj1235 A/B Problem(扩展欧几里德求逆元)

1000 ms  |  内存限制： 65535

描述

已知：

1. n = (A % 9973); 2. gcd(B, 9973) = 1;

计算：

(A / B) % 9973

输入

数据的第一行是一个T，表示有T组数据.

每组数据有两个数n(0 <= n < 9973)和B(1 <= B <= 10^9).

输出

对应每组数据输出(A / B) % 9973.

样例输入

2 1000 53 87 123456789

样例输出

7922 6060

#include const int MOD=9973;typedef long long LL;int extend_Eculid(LL a,LL b,LL &x,LL &y){ if(b==0) { x=1; y=0; return a; } LL r=extend_Eculid(b,a%b,y,x); y-=a/b*x; return r;}//模版而已 对于这道题 一定有解 LL solve(LL b,LL MOD){ LL x,y,res; LL gcd=extend_Eculid(b,MOD,x,y); if(1%gcd) return -1; //无解 if(MOD<0) MOD=-MOD;//如果MOD为负 x=x*1/gcd; res=x%MOD; if(res<0) res+=MOD; return res; }int main(){ int t; scanf("%d",&t); while(t--) { LL n,b; scanf("%lld %lld",&n,&b); LL r=solve(b,MOD); printf("%lld\n",(n*r)%MOD); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。