Cod sursa(job #304378)
| Utilizator | Data | 12 aprilie 2009 13:02:12 | |
|---|---|---|---|
| Problema | Invers modular | Scor | 100 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.49 kb |
#include<stdio.h>
void cmmdc(long long&,long long&,long long,long long);
long long a,b;
int main(){
freopen("inversmodular.in","r",stdin);
freopen("inversmodular.out","w",stdout);
scanf("%lld %lld",&a,&b);
long long t1=0,t2;
cmmdc(t1,t2,a,b);
if(t1<=0)
t1=b+t1%b;
printf("%lld\n",t1);
return 0;
}
void cmmdc(long long&t1,long long &t2,long long a,long long b){
if(b==0){
t1=1;
t2=0;}
else{
long long t0;
cmmdc(t1,t2,b,a%b);
t0=t1;
t1=t2;
t2=t0-(a/b)*t2;}
}