Modular Inverse

浅浅的花香味﹌ 2022-06-17 07:56 150阅读 0赞

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 ####

3
    3 11
    4 12
    5 13

#### Sample Output ####

4
    Not Exist
     8 题意：给出a和m，求出a的最小逆元，即求形如ax+my=1的方程组（直接上扩展欧几里得模板） 逆元存在的条件是：a和m的最大公约数为1，否则不存在 （x可能为负数，所以x % m也一样是负值，此时保持在[-(m-1), 0]内，正值则保持在[0, m-1]内。 加上m就保持在[1, 2m - 1]内，所以再模一下m就在[0, m-1]内了）。 #include <iostream>
    #include<algorithm>
    #include<cstdio>
    #include<cmath>
    using namespace std;
    int x,y;
    /*int A(int a,int b)
    {
        return b==0?a:A(b,a%b);
    }*/
    int AA(int a,int b,int &x,int &y)
    {
        if(b==0)
        {
            x=1;
            y=0;
            return a;
        }
        int r=AA(b,a%b,x,y);
        int temp=x;
        x=y;
        y=temp-a/b*y;
        return r;
    }
    int main()
    {
        int n,a,b,c;
        scanf("%d",&n);
        while(n--)
        {
            x=0;
            y=0;
            scanf("%d %d",&a,&b);
            /*if(A(a,b)!=1)//代码都AC
                printf("Not Exist\n");
            else
            {
                AA(a,b,x,y);
                x>0?printf("%d\n",x):printf("%d\n",x+abs(b));
            }*/
            int rr=AA(a,b,x,y);
            if(rr!=1)
                printf("Not Exist\n");
            else
                x>0?printf("%d\n",x):printf("%d\n",x+abs(b));//当求得为负数时，就再加上模的绝对值即可
        }
        return 0;
    }