Cod sursa(job #1230612)
Utilizator | Soare Roxana Florentina roxana_97 | Data | 18 septembrie 2014 17:44:33 |
---|---|---|---|
Problema | Invers modular | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.5 kb |
#include<fstream>
using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
long long N,A,X,Y;
long long gcd(long long a,long long b,long long &x,long long &y)
{
if(!b){
x=1;
y=0;
return a;
}
long long x0,y0,D;
D=gcd(b,a%b,x0,y0);
x=y0;
y=x0-(a/b)*y0;
return D;
}
int main()
{
long long A,N,inv,ins;
f>>A>>N;
gcd(A,N,inv,ins);
while(inv<=0) inv+=N;
g<<inv<<'\n';
return 0;
}