Cod sursa(job #2204509)
Utilizator | macovei tiberiu MacoveiTiberiu | Data | 16 mai 2018 08:45:27 |
---|---|---|---|
Problema | Invers modular | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.47 kb |
#include<iostream>
using namespace std;
long long int p(long long int a, long long int b){
if(b==0) return 1;
if(b==1) return a;
long long int t=p(a, b/2);
return t*t*p(a, b%2);
}
int a, n, v[1000];
int main(){
cin>>a>>n;
v[1]=1;
for(int i=2;i<=n;i++){
v[i]=i-1;
}
for(int i=2;i<=n;i++){
for(int j=i+i;j<=n;j+=i){
v[j]-=v[i];
}
}
cout<<p(a, v[n]-1)%n;
}