J - Modular Inverse ZOJ - 3609 【求逆元，拓展欧几里得】

Lokinli

发布于 2023-03-09 15:07:41

2990

发布于 2023-03-09 15:07:41

文章被收录于专栏：以终为始

J - Modular Inverse

The modular modular multiplicative inverse of an integer a modulo m is an integer xsuch 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

Sample Output

4
Not Exist
8

&：1 的逆元就是 1。

//#include <bits/stdc++.h>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <iostream>
#define rep(i,a,b) for(int i = (a); i < (b); i ++)
#define per(i,a,b) for(int i = (a); i > (b); i --)
#define MM(a) memset(a,0,sizeof(a))
#define pb push_back
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const ll maxn = 300;
const ll mod = 1e9 + 7;
ll extend_gcd(ll a, ll b, ll &x, ll &y)
{
    if(b==0)
    {
        x=1ll;
        y=0;
        return a;
    }
    else
    {
        ll r = extend_gcd(b,a%b,y,x);
        y-=x*(a/b);
        return r;
    }
}
vector<ll>line_mod(ll a,ll b,ll n)
{
    ll x,y;
    ll d=extend_gcd(a,n,x,y);
    vector<ll>ans;
    ans.clear();
    if(b%d==0)
    {
        x%=n;
        x+=n;
        x%=n;
        ans.push_back(x*(b/d)%(n/d));
        for(ll i=1; i<d; ++i)
        {
            ans.push_back((ans[0]+i*n/d)%n);
        }
    }
    return ans;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        ll a,m;
        scanf("%lld %lld",&a,&m);
        vector<ll>ans = line_mod(a,1ll,m);
        sort(ans.begin(), ans.end());
        if(ans.empty())printf("Not Exist\n");
        else if(ans[0] == 0) printf("1\n");
        else printf("%lld\n",ans[0]);
    }
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2019-04-26，如有侵权请联系 cloudcommunity@tencent.com 删除

case