Cod sursa(job #948426)
Utilizator | Christescu Matei matei_c | Data | 10 mai 2013 12:37:59 |
---|---|---|---|
Problema | Invers modular | Scor | 50 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.52 kb |
#include<fstream>
using namespace std ;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
int b, n ;
int x, y ;
void euclid(int a, int b, int &x, int &y )
{
if( b == 0 )
{
x = 1 ;
y = 0 ;
}
else
{
int x0, y0 ;
euclid( b, a % b, x0, y0 ) ;
x = y0 ;
y = ( x0 - ( ( long long )( a / b ) * y0) % n ) % n ;
}
}
int main()
{
fin >> b >> n ;
euclid( n, b, x, y ) ;
fout << y ;
return 0 ;
}