Submission details
Task:Finding inverse
Sender:aalto26kh_014
Submission time:2026-11-13 19:05:38 +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 <bits/stdc++.h>
using namespace std;

// debug
template<class T> ostream& operator<<(ostream&, const vector<T>&);
template<class T> ostream& operator<<(ostream&, const set<T>&);
template<class T> ostream& operator<<(ostream&, const multiset<T>&);
template<class K, class V> ostream& operator<<(ostream&, const map<K, V>&);
template<class T, size_t N> ostream& operator<<(ostream&, const array<T, N>&);
template<class A, class B> ostream& operator<<(ostream& os, const pair<A, B>& p) { return os << "(" << p.first << ", " << p.second << ")"; }
template<class T>
void print_collection(ostream& os, const T& v) {
    os << "{";
    bool first = true;
    for (const auto& x : v) {
        if (!first) os << ", ";
        first = false;
        os << x;
    }
    os << "}";
}
template<class T> ostream& operator<<(ostream& os, const vector<T>& v) { print_collection(os, v); return os; }
template<class T> ostream& operator<<(ostream& os, const set<T>& v) { print_collection(os, v); return os; }
template<class T> ostream& operator<<(ostream& os, const multiset<T>& v) { print_collection(os, v); return os; }
template<class K, class V> ostream& operator<<(ostream& os, const map<K, V>& v) { print_collection(os, v); return os; }
template<class T, size_t N> ostream& operator<<(ostream& os, const array<T, N>& v) { print_collection(os, v); return os; }
#define dbg(x) cerr << #x << " = " << (x) << '\n'

using ll = long long;
constexpr int INF = 1'000'000'000; // 1e9
constexpr ll LINF = 1'000'000'000'000'000'000LL; // 1e18
constexpr int MOD = 1'000'000'007; // 1e9 + 7

inline ll add(ll a, ll b) { return (a + b) % MOD; }
inline ll sub(ll a, ll b) { return ((a - b) % MOD + MOD) % MOD; }
inline ll mul(ll a, ll b) { return (a * b) % MOD; }

int modpow(int x, int n, int m) {
    if (n == 0) return 1%m;
    ll u = modpow(x,n/2,m);
    u = (u*u)%m;
    if (n%2 == 1) u = (u*x)%m;
    return u;
}

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

int eulerTotient(int n) {
    ll result = n;

    for (ll p = 2; p <= n / p; p++) {
        if (n % p == 0) {
            while (n % p == 0)
                n /= p;

            result -= result / p;
        }
    }

    if (n > 1)
        result -= result / n;

    return result;
}

void solve() {
    int a, m;
    cin >> a >> m;

    a %= m;

    if (gcd(a, m) != 1) {
        cout << -1;
        return;
    }

    cout << modpow(a, eulerTotient(m)-1, m);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();

    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