Pagini recente » Cod sursa (job #356743) | Cod sursa (job #1028181) | Cod sursa (job #934498) | Cod sursa (job #169626) | Cod sursa (job #2492364)
#include <fstream>
using namespace std;
ifstream cin("inversmodular.in");
ofstream cout("inversmodular.out");
int euler(int n){
long long d = 2, p, prod = n;
while ( d * d <= n ) {
p = 0;
while ( n % d == 0 ) {
n /= d;
p ++;
}
if ( p )
prod = prod / d * ( d - 1 );
d ++;
}
if ( n > 1 )
prod = prod / n * ( n - 1 );
return prod;
}
int putere(int a,int n,int m){
int prod = 1;
do{
if(n%2 != 0){
prod = (long long)prod * a % m;
}
a = 1LL * a * a % m;
n /= 2;
}while(n != 0);
return prod;
}
int main()
{
int a,n,x;
cin >> a >> n;
x = putere(a,euler(n) - 1,n);
cout << x;
return 0;
}