Cod sursa(job #948417)
Utilizator | Data | 10 mai 2013 11:51:44 | |
---|---|---|---|
Problema | Invers modular | Scor | 60 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.56 kb |
#include<fstream>
using namespace std ;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
int a, n ;
int mod ;
int putere(int a, int n)
{
if( n == 0 )
return 1 ;
if( n == 1 )
return a % mod ;
int X = ( long long )( putere( a, n / 2 ) % mod ) ;
if( n % 2 == 0 )
return ( (long long)X * X ) % mod ;
else
return ( ( ( (long long)X * X ) % mod ) * a ) % mod ;
}
int main()
{
fin >> a >> n ;
mod = n ;
fout << putere( a, n - 2 ) ;
return 0 ;
}