a289: Modular Multiplicative Inverse

內容 ：
    一整數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

程式碼 ：

#include<stdio.h>

int main()
{
    int a, n, quotient, remainder, temp_a, temp_b, temp_c, temp_n;
    
    while(scanf("%d%d",&a,&n)==2)
    {
        if(n == 1)
        {
            printf("No Inverse\n");
            continue;
        }
        
        temp_n = n;
        temp_a = 0;
        temp_b = 1;
        temp_c = 1;
        
        while(1)
        {
            quotient = temp_n / a;
            remainder = temp_n % a;
            if(remainder == 0)
            {
                if(a == 1)
                    printf("%d\n",temp_c<0?(temp_c+n):temp_c);
                else
                    printf("No Inverse\n");
                break;
            }
            temp_n = a;
            a = remainder;
            
            temp_c = (temp_a - quotient*temp_b) % n;
            
            temp_a = temp_b;
            temp_b = temp_c;
        }
    }
    
    return 0;
}

http://zerojudge.tw/ShowProblem?problemid=a289