A/B——同余定理+逆元（除法逆元）

2019-04-14 12:23发布

站内文章 / 模拟电子
10539 0 1179
class="markdown_views prism-tomorrow-night"> 同余定理:
数论中的重要概念。给定一个正整数m，如果两个整数a和b满足a-b能够被m整除，即(a-b)/m得到一个整数，那么就称整数a与b对模m同余，记作a≡b ( modm)" role="presentation" style="position: relative;">a≡b ( modm)。对模m同余是整数的一个等价关系
(a+b ) % c=(a % c+b % c) % c" role="presentation">(a+b ) % c=(a % c+b % c) % c
(a ∗ b) % c=(a % c ∗ b % c) % c" role="presentation">(a ∗ b) % c=(a % c ∗ b % c) % c
令
a=k1∗m+r1b=k2∗m+r2" role="presentation">a=k1∗m+r1b=k2∗m+r2 (811)(a+b) % m=((k1∗m+r1)+(k2∗m+r2)) % m(812)=((k1+k2)∗m+(r1+r2)) % m(813)=(r1+r2) % m(814)=(a % m+b % m) % m" role="presentation">(811)(a+b) % m=((k1∗m+r1)+(k2∗m+r2)) % m(812)=((k1+k2)∗m+(r1+r2)) % m(813)=(r1+r2) % m(814)=(a % m+b % m) % m 所以
(a+b) % m=(a % m+b % m)" role="presentation">(a+b) % m=(a % m+b % m)
要求(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
令m=9973" role="presentation" style="position: relative;">m=9973那么
(815)AB %;m=AB∗1 %m(816)=AB∗B∗C%m" role="presentation">(815)AB %;m=AB∗1 %m(816)=AB∗B∗C%m
即
B∗C%m=1" role="presentation">B∗C%m=1
B∗C≡1modm" role="presentation">