Submission details
Task:Finding inverse
Sender:aalto26kh_015
Submission time:2026-11-14 01:37:29 +0200
Language:C++ (C++20)
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.00 sdetails
#2ACCEPTED0.00 sdetails
#3ACCEPTED0.00 sdetails
#4ACCEPTED0.00 sdetails
#5ACCEPTED0.00 sdetails
#6ACCEPTED0.00 sdetails
#7ACCEPTED0.00 sdetails
#8ACCEPTED0.00 sdetails
#9ACCEPTED0.00 sdetails
#10ACCEPTED0.00 sdetails
#11ACCEPTED0.00 sdetails
#12ACCEPTED0.00 sdetails
#13ACCEPTED0.00 sdetails
#14ACCEPTED0.00 sdetails

Code

#include <iostream>
#include <unordered_map>
#include <math.h>
using namespace std;
typedef long long ll;
typedef unordered_map<int, int> iiMap;

ll ModPow(ll base, ll ex, ll mod) {
    if (ex == 0) return 1 % mod;
    ll tmp = ModPow(base, ex/2, mod);
    tmp = (tmp * tmp) % mod;
    if (ex % 2 == 1) tmp = (tmp *  base) % mod;
    return tmp;
}

iiMap factors(ll val) {
    iiMap fac;  // fac: count
    
    for (int x = 2; x*x <= val; x++) {
        while (val%x == 0) {
            if (!fac.count(x)) {
                fac[x] = 0;
            }
            fac[x]++;
            val /= x;
        }
    }
    if (val > 1) {
        if (!fac.count(val)) {
            fac[val] = 0;
        }
        fac[val]++;
    }
    return fac;
}

ll phi(ll val) {
    if (val < 1) return 0;
    iiMap facs = factors(val);
    ll total = 1;
    for (auto kv: facs) {
        total *= powl(kv.first, kv.second - 1) * (kv.first - 1);
    }
    return total;
}

ll ModInv(ll val, ll mod) {
    ll pm = phi(mod);
    return ModPow(val, pm - 1, mod);
}

ll gcd(ll a, ll b) {
    if (b == 0) return a;
    return gcd(b, a%b);
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

    ll a, m;
    cin >> a >> m;
    if (a == 0 || gcd(a, m) != 1) {
        cout << "-1\n";
        return 0;
    }
    cout << ModInv(a, m) << "\n";

    return 0;
}

Test details

Test 1

Verdict: ACCEPTED

input
6 7

correct output
6

user output
6

Test 2

Verdict: ACCEPTED

input
0 7

correct output
-1

user output
-1

Test 3

Verdict: ACCEPTED

input
5 78

correct output
47

user output
47

Test 4

Verdict: ACCEPTED

input
89 99

correct output
89

user output
89

Test 5

Verdict: ACCEPTED

input
0 61

correct output
-1

user output
-1

Test 6

Verdict: ACCEPTED

input
897 947

correct output
625

user output
625

Test 7

Verdict: ACCEPTED

input
419 538

correct output
217

user output
217

Test 8

Verdict: ACCEPTED

input
32 938

correct output
-1

user output
-1

Test 9

Verdict: ACCEPTED

input
184120 505187

correct output
438779

user output
438779

Test 10

Verdict: ACCEPTED

input
264601 885661

correct output
360221

user output
360221

Test 11

Verdict: ACCEPTED

input
40310 590135

correct output
-1

user output
-1

Test 12

Verdict: ACCEPTED

input
202254499 577081420

correct output
128866679

user output
128866679

Test 13

Verdict: ACCEPTED

input
539836073 888851205

correct output
797044652

user output
797044652

Test 14

Verdict: ACCEPTED

input
697847215 756971670

correct output
-1

user output
-1