ZOJ 3609 Modular Inverse 解線性模方程

modular inverse

time limit: 2 seconds      memory limit: 65536 kb

the modular modular multiplicative inverse of an integer a modulo m is an integer x such that <code>a-1≡x (mod m)</code>.

this is equivalent to <code>ax≡1 (mod m)</code>.

there are multiple test cases. the first line of input is an integer t ≈ 2000 indicating the number of test cases.

each test case contains two integers 0 &lt; a ≤ 1000 and 0 &lt; m ≤ 1000.

for each test case, output the smallest positive x. if such x doesn‘t exist, output "not exist".

模線性方程ax=b (mod n)，令d=exgcd(a,n),該方程有解的充要條件為 d | b ，即 b% d==0

方程ax=b(mod n)的最小解 :x=(x*(b/d))%n 

方程ax=b(mod n)的最整數小解: x=(x%(n/d)+n/d)%(n/d)

因為要求輸出最小整數，是以如果答案為0的話，肯定是m=1的情況，此情況應輸出1.