Cod sursa(job #3295982)
| Utilizator | Data | 10 mai 2025 12:43:40 | |
|---|---|---|---|
| Problema | Invers modular | Scor | 60 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 0.54 kb |
#include <fstream>
using namespace std;
#define ll long long
ll exponentiation_by_sq(ll n, ll p, ll orig_n) {
if (p == 0)
return 1;
if (p % 2 == 0)
return exponentiation_by_sq(n * n % orig_n, p / 2, orig_n) ;
if (p % 2 == 1) {
return n * exponentiation_by_sq(n * n %orig_n, (p - 1) / 2, orig_n) % orig_n;
}
return 1;
}
int main() {
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
ll a, n;
fin>>a>>n;
fout<<exponentiation_by_sq(a, n - 2, n);
return 0;
}