nyoj1235 AB Problem(扩展欧几里德求逆元)

时间限制： 1000 ms  |  内存限制： 65535 KB 难度： 3 描述

已知：

    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

欧几里德模板题。。 A÷Bmod9973 可以化简为 n×B′mod9973 . B′ 为 B的逆元, 可以通过 B×x+9973×y=1 得到。

#include <stdio.h> 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; }