zoj3609

maksyuki 发表于 oj 分类，标签: 数论-乘法逆元

11 9月 2015

Modular Inverse

The modular modular multiplicative inverse of an integer a modulo m is an integer x such that a^-1≡x (mod m). This is equivalent to ax≡1 (mod m).

Input

There are multiple test cases. The first line of input is an integer T ≈ 2000 indicating the number of test cases.

Each test case contains two integers 0 < a ≤ 1000 and 0 < m ≤ 1000.

Output

For each test case, output the smallest positive x. If such x doesn't exist, output "Not Exist".

Sample Input

33 114 125 13

Sample Output

4Not Exist8

Author: WU, Zejun
Contest: The 9th Zhejiang Provincial Collegiate Programming Contest

题目类型：乘法逆元

算法分析：直接使用乘法逆元求解即可，注意本题要求求解的是最小正值，而不是最小非负值！！！

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define LL long long

const int INF = 0x7FFFFFFF;
const int MOD = 1e9 + 7;
const double EPS = 1e-6;
const double PI = 2 * acos (0.0);
const int maxn = 1e6 + 66;

long long gcd_ex (long long a, long long b, long long &x, long long &y)
{
    if (b == 0) { x = 1; y = 0; return a; }
    long long d = gcd_ex (b, a % b, y, x);
    y = y - a / b * x;
    return d;
}

long long mod_equ (long long a, long long b, long long c)
{
    long long x, y;
    long long d = gcd_ex (a, b, x, y);

    if (c % d)
        return -1;

    x = (x * c / d) % (b / d);
    if (x <= 0)
        x += b / d;

    return x;
}

int main()
{
//    CPPFF;
    LL aa, mm, tt;
    cin >> tt;

    while(tt--)
    {
        cin >> aa >> mm;
        LL tt = mod_equ (aa, mm, 1);

        if (tt == -1)
            cout << "Not Exist" << endl;

        else
            cout << tt << endl;
    }
    return 0;
}

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define LL long long

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-6;

const double PI = 2 * acos (0.0);

const int maxn = 1e6 + 66;

long long gcd_ex (long long a, long long b, long long &x, long long &y)

{

if (b == 0) { x = 1; y = 0; return a; }

long long d = gcd_ex (b, a % b, y, x);

y = y - a / b * x;

return d;

}

long long mod_equ (long long a, long long b, long long c)

{

long long x, y;

long long d = gcd_ex (a, b, x, y);

if (c % d)

return -1;

x = (x * c / d) % (b / d);

if (x <= 0)

x += b / d;

return x;

}

int main()

{

// CPPFF;

LL aa, mm, tt;

cin >> tt;

while(tt--)

{

cin >> aa >> mm;

LL tt = mod_equ (aa, mm, 1);

if (tt == -1)

cout << "Not Exist" << endl;

else

cout << tt << endl;

}

return 0;

}

zoj3203

vijos1098

一	二	三	四	五	六	日
« 6月
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30

超客的水墨烟雨

zoj3609

分类目录

标签云

书签

近期评论