Morris' Blog

2011-11-12 06:48:53Morris

a289. Modular Multiplicative Inverse

留言 1 收藏 0 推薦 0

內容：

一整數a 對模數n之模反元素是指滿足以下公式的整數 b
a-1 ≡ b        (mod n)
也可以寫成以下的式子
ab ≡ 1        (mod n)                      
現在給定兩個數字a, n，求一個最小正整數 b，若不存在則輸出” No Inverse”

輸入說明：

有多筆測資，每組第一行有兩個數字 a, n，(1 ≦ a, n ≦ 100,000,000)

輸出說明：

一個最小正整數 b，若不存在則輸出” No Inverse”

範例輸入：

79 62
96 47
49 28

範例輸出：

11
24
No Inverse

提示：

出處：

 
  Discrete Mathematics
  
    (管理：morris1028)

作法 ： GCD
利用輾轉相除法, 小心 n = 1, 此時答案皆為 No Inverse

/**********************************************************************************/
/* Problem: a289 "Modular Multiplicative Inverse" from Discrete Mathematics      */
/* Language: C (606 Bytes)                                                       */
/* Result: AC(140ms, 308KB) judge by this@ZeroJudge                              */
/* Author: morris1028 at 2011-11-11 11:50:24                                     */
/**********************************************************************************/

#include<stdio.h>
int Calu_Mod_Inverse(int x, int y) {
   int t, mod = y;
   int ra = 1, rn = 0, la = 0, ln = 1, step = 1;
   while(x%y) {
       if(step) {
           ra -= x/y * la;
           rn -= x/y * ln;
       } else {
           la -= x/y * ra;
           ln -= x/y * rn;
       }
       t = x, x = y, y = t%y;
       step = 1 - step;
   }
   if(y == 1) {
       if(step)
           return (la%mod + mod)%mod;
       else
           return (ra%mod + mod)%mod;
   }
   else
       return 0;
}
int main() {
   int a, n, tmp;
   while(scanf("%d %d", &a, &n) == 2) {
       tmp = Calu_Mod_Inverse(a, n);
       if(tmp)       printf("%d\n", tmp);
       else       puts("No Inverse");
   }
   return 0;
}

上一篇：a274. 友誼的數字

下一篇：a269. 小氣的國王