C - A/B
题目
要求(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
思路：除法求余，(A/B)%9973=A%9973+B^-1%9973，题目就转化为求B的逆元，因为B与9973互质，所以可以根据费马小定理，
a^(p-1)≡1modp(a与p互质)来求B的逆元。
再用快速幂求就行了。
代码
#include <cstdio> #include <cstring> const int mod=9973; int func(int x){int n=mod-2,res=1;while(n>0){if(n&1) res=res*x%mod;x=(long long)x*x%mod;n/=2;}return res; } int main(){int t,n,b;scanf("%d",&t);while(t--){scanf("%d%d",&n,&b);if(n==0) puts("0");else{long long res=(long long)n*func(b);printf("%lld\n",res%mod);}}return 0; }
12345678910111213141516171819202122232425
