主題
題目連結：
題目大意：
給定兩正整數ａ、ｎ（１ ≦ ａ、ｎ ≦ １００, ０００, ０００），找到一個ｂ滿足：
ａｂ ≡ １ （ｍｏｄ ｎ）
若找不到ｂ滿足上式，則輸出「No Inverse」。
範例輸入：
79 62
96 47
49 28
範例輸出：
11
24
No Inverse
解題思維：
可以參考ＷＩＫＩ頁面下的模反元素，以便查看更詳盡的相關證明。
簡單來講，ａ ％ ｎ（取ｎ的餘數，等同 ｍｏｄ ｎ）有模反元素的充分條件為：ａ、ｎ的最大公因數為１，即ＧＣＤ（ａ, ｎ）＝１。
因為根據「擴展歐幾里得算法」，我們可以找到ｘ、ｙ滿足：
ａｘ ＋ ｂｙ ＝ ＧＣＤ（ａ, ｂ）
將上式寫成我們在這題所需的形式即為：
ａｘ ＋ ｎｙ ＝ ＧＣＤ（ａ, ｎ）
而把等式左右兩邊同取ｎ的餘數：
ａｘ ≡ ＧＣＤ（ａ, ｎ）（ｍｏｄ ｎ）
以上我們可以看到，當ａ跟ｎ互質時，上式的ｘ就是我們要找的模反元素（因為ＧＣＤ（ａ, ｎ）＝１）。
因此使用上述提到的擴展歐幾里得算法，在算ＧＣＤ的時候，順便把輾轉相除法的關係式存起來。然後判斷ＧＣＤ的值。如果是１，剛剛存下來的關係式便是所求；反之，不是１就不存在模反元素。
達人