题意

求a*x ≡ 1（mod m），求最小的正整数 x ，如果没有解输出 “Not Exist”。

思路

求乘法逆元。a*x ≡ 1（mod m）转化为 ，求最小的正！整数 x 。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
void exgcd(int a, int b, int& d, int& x, int& y)
{
    if (!b) { d=a; x=1; y=0; }
    else { exgcd(b, a%b, d, y, x); y -= x*(a/b); }
}
int cal(int a, int b, int c)
{
    int GCD, x0, y0;
    exgcd(a, b, GCD, x0, y0);
    if (c%GCD) return -1;
    x0 *= c/GCD;
    int ans = (x0%b+b)%b;
    return ans?ans:b;
}
int main()
{
    int T; scanf("%d", &T);
    while (T--)
    {
        int a, m; scanf("%d%d", &a, &m);
        int ans = cal(a, m, 1);
        if (ans != -1) printf("%d\n", ans);
        else printf("Not Exist\n");
    }
    return 0;
}
/*
3
3 11
4 12
5 13
*/