Pagini recente » Cod sursa (job #2567840) | Cod sursa (job #3122444) | Cod sursa (job #2401482) | Cod sursa (job #2533540) | Cod sursa (job #2495169)
#include <iostream>
#include <fstream>
using namespace std;
ifstream in ("inversmodular.in");
ofstream out ("inversmodular.out");
long long int logpow (long long int a, long long int n) {
long long int p = 1;
while (n > 0) {
if (n % 2 == 1) {
p *= a;
}
a *= a;
n /= 2;
}
return p;
}
long long int phi (long long int n) {
long long int p = 2, k, rez = 1;
while (p * p <= n) {
k = 0;
while (n % p == 0) {
n /= p;
k ++;
}
if (k > 0) {
rez *= logpow (p, k - 1) * (p - 1);
}
p ++;
}
if (n > 1) {
rez *= (n - 1);
}
return rez;
}
int main() {
long long int a, n;
long long int rez;
in >> a >> n;
rez = logpow (a, phi (n) - 1) % n;
out << rez;
return 0;
}