Cod sursa(job #2132290)
| Utilizator | Data | 15 februarie 2018 17:35:15 | |
|---|---|---|---|
| Problema | Invers modular | Scor | 100 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.6 kb |
#include <cstdio>
#define ll long long
using namespace std;
ll a,n;
void Read()
{
freopen("inversmodular.in","r",stdin);
scanf("%lld%lld",&a,&n);
}
inline void cmmdc(ll a,ll b,ll &x,ll &y)
{
if (b==0)
{
x=1;
y=0;
}
else
{
cmmdc(b,a%b,x,y);
ll aux=x;
x=y;
y=aux-y*(a/b);
}
}
void Write()
{
ll inv,y;
freopen("inversmodular.out","w",stdout);
cmmdc(a,n,inv,y);
if (inv<0) inv=inv%n+n;
printf("%lld",inv);
}
int main()
{
Read();
Write();
return 0;
}
