题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=1576
思路转自：http://blog.csdn.net/zxjcarrot/article/details/20798021?locationNum=9
模运算有很多性质:(a+b) % c==(a % c + b % c) %c , (a-b) % c==(a % c - b % c) % c, (a*b) % c==(a % c * b % c) % c,遗憾的是除法没有这个性质.
不过可以通过求B的乘法逆元来求得.
解法:(a / b) % c == a * b^(-1) % c 其中b^(-1)为b的乘法逆元,乘法逆元可以通过拓展欧几里得算法求得.
推导:(a / b) ≡ x (mod c) ==>两边乘上一个b得到a ≡ bx (mod c) ==>两边乘上b mod n的乘法逆元得到 ==>a * b^(-1) ≡ b * b^(-1) * x (mod c) ==> a * b^(-1) ≡ x (mod c)
这种方法只能在gcd(b,c)为1的情况下使用,题目正好符合这个情况.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
LL PowMod(LL x,LL n,LL p) //x^n 对p取模
{int result=1;int base = x%p; while(n>0){if(n & 1)result=(result*base)%p; //当二进制不为0时，就要乘个 base=(base*base)%p; //累乘此时二进制的权值 n>>=1;}return result;
}
int main()
{LL T,A,B; cin>>T;while(T--){cin>>A>>B;int NB=PowMod(B,9971,9973);cout<<(A*NB)%9973<<endl;}return 0;
}