ZOJ 3609 Modular Inverse

Description

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

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

Output

For each test case, output the smallest positive x. If such x

Sample Input

3
3 11
4 12
5 13      

Sample Output

References

• ​​http://en.wikipedia.org/wiki/Modular_inverse​​
• 注意mod 1的逆元是1

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<set>
#include<ctime>
#include<vector>
#include<cmath>
#include<algorithm>
#include<map>
#define ll long long
using namespace std;
const int maxn = 1e5 + 10;
int T, n, m;

void egcd(int a, int b, int &x, int &y)
{
  if (b == 0){ x = 1, y = 0; return; }
  egcd(b, a % b, x, y);

  long long t = x;
  x = y, y = t - a / b * y;
}

int main()
{
  scanf("%d", &T);
  while (T--)
  {
    scanf("%d%d", &n, &m);
    if (m == 1)
    {
      printf("1\n");
      continue;
    }
    int x, y;
    egcd(n, m, x, y);
    x = (x % m + m) % m;
    if (n*x%m == 1)printf("%d\n", x);
    else printf("Not Exist\n");
  }
  return 0;
}