本文共 1279 字，大约阅读时间需要 4 分钟。

nyoj1235A/B 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

#include
   
    const int mod = 9973;//(A / B) % mod;//n = A % mod;//b为B关于mod的逆元 //b = B^(mod-2);//(A / B) % mod = (A * b) % mod = (A%mod * b%mod) % mod = (n * b%mod) % mod //https://www.cnblogs.com/linyujun/p/5194184.html//https://www.cnblogs.com/zzqc/p/7192436.html //http://blog.csdn.net/f_zyj/article/details/71156809void extendGcd(long long a, long long b, long long * s, long long * t);long long modReverse(long long a, long long n);int main() {  int times;  long long n, B;  scanf("%d", ×);  while (times--) {    scanf("%lld%lld", &n, &B);     long long b = modReverse(B, mod);    printf("%d\n", (n * b) % mod);  }  return 0;}void extendGcd(long long a, long long b, long long * s, long long * t) {  if (b == 0) {      *s = 1, *t = 0;    }else {      long long next_s, next_t;      extendGcd(b, a % b, &next_s, &next_t);      *s = next_t, *t = next_s - a/b * next_t;    }}long long modReverse(long long a, long long n) {  //a与n互质时，才存在a关于n逆元   long long s, t;  extendGcd(a, n, &s, &t);  return (s + n) % n;//防止s可能为负数}