Pagini recente » Cod sursa (job #2893789) | Monitorul de evaluare | Cod sursa (job #2556390)
#include <fstream>
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
//invers modular I - phi(n)
//euler -> a^phi(n) = 1 (mod n), gcd(a, n) = 1
typedef unsigned long long mare;
int phi(int n)
{
int rez = n;
int d;
for (d = 2; d*d<n; d++)
if (n%d == 0)
{
rez = rez / d * (d-1);
rez = rez / (n/d) * (n/d-1);
}
if (d*d == n)
rez = rez / d * (d-1);
if (rez == n)
return n-1;
return rez;
}
int invmod(int a, int n)
{
//a^-1 % n
int e = phi(n)-1;
mare b = a, rez = 1;
while (e > 0)
{
if (e&1)
rez = rez * b % n;
b = b*b % n;
e >>= 1;
}
return rez;
}
int main()
{
int a, n;
fin >> a >> n;
fout << invmod(a, n);
return 0;
}