Submission details
Task:Finding inverse
Sender:aalto26kh_015
Submission time:2026-11-14 01:35:27 +0200
Language:C++ (C++20)
Status:COMPILE ERROR

Compiler report

input/code.cpp: In function 'll phi(ll)':
input/code.cpp:41:18: error: 'powl' was not declared in this scope
   41 |         total *= powl(kv.first, kv.second - 1) * (kv.first - 1);
      |                  ^~~~

Code

#include <iostream>
#include <unordered_map>
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;
}