給你 n 和 a, b。

求出 (a', b') , 使得 任一組 (x, y) 且 (a*x+b*y)%n=0 時,(a'*x+b'*y)%n=0。

a*x + b*y % n = 0

->((a*x+b*y) * i) % n = 0

-> (a*i%n)*x + (b*i%n)*y

所以只要 枚舉i -> (a', b') = (a*i%n, b*i%n),直到 (a', b')=(0, 0) 為止。

要 照大小 輸出,其實要用 sort 的,想說太久沒用 heap,就用了一下。

我的code

http://snipt.org/zfhfj3

 

文章標籤
創作者介紹
創作者 jghs1328 的頭像
jghs1328

jghs1328

jghs1328 發表在 痞客邦 留言(0) 人氣()