大神的世界

中國餘數定理相關

 

#include <iostream>
#include <stack>

using namespace std;

int find_inverse(int a, int n){

    if(n == 1)
        return 0;

    int tmp1, tmp2, tmp;
    stack<int> qstack;

    tmp1 = a;
    tmp2 = n;

    while(1){
        if(!tmp1 || !tmp2)
            return 0;

        if(tmp1 == 1 || tmp2 == 1)
            break;

        if(tmp1 >= tmp2){
            qstack.push(-tmp1/tmp2);
            tmp1 %= tmp2;
        }
        else
            swap(tmp1, tmp2);
    }

    if(qstack.empty())
        return 1;

    tmp1 = 1;
    tmp2 = qstack.top();
    qstack.pop();

    while(!qstack.empty()){
        tmp = tmp2;
        tmp2 = tmp1 + tmp2*qstack.top();
        tmp1 = tmp;
        qstack.pop();
    }

    if(a > n)
        return tmp1;
    else
        return tmp2;
}

int main()
{
    int a, n;
    int answer;

    while(cin >> a >> n){
        answer = find_inverse(a, n);

        if(answer){
            while(answer < 0)
                answer += n;

            cout << answer%n << endl;
        }
        else
            cout << "No Inverse\n";
    }
    return 0;
}