Submission details
Task:Finding inverse
Sender:Dereden
Submission time:2025-11-13 14:49:15 +0200
Language:C++ (C++17)
Status:COMPILE ERROR

Compiler report

input/code.cpp: In function 'int totient(std::unordered_map<int, int>&)':
input/code.cpp:27:16: error: 'pow' was not declared in this scope
   27 |         res *= pow(p.first, p.second-1)*(p.first-1);
      |                ^~~

Code

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <climits>
#include <numeric>

typedef long long ll;

using namespace std;

unordered_map<int, int> factors(int n) {
    unordered_map<int, int> f;
    for (int x = 2; x*x <= n; x++) {
        while (n%x == 0) {
            f[x]++;
            n /= x;
        }
    }
    if (n > 1) f[n]++;
    return f;
}

int totient(unordered_map<int, int>& f) {
    int res = 1;
    for (const auto& p : f) {
        res *= pow(p.first, p.second-1)*(p.first-1);
    }
    return res;
}

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

int modinverse(int x, int m) {
    if (gcd(x, m) != 1) return -1;
    auto f = factors(m);
    int t = totient(f);
    return modpow(x, t-1, m);
}

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

    // freopen("input.txt", "r", stdin); // TODO: REMOVE THIS YOU STUPID ****

    int n, m;
    cin >> n >> m;
    cout << modinverse(n, m);
    return 0;
}