Cod sursa(job #673306)
Utilizator | Data | 4 februarie 2012 11:51:33 | |
---|---|---|---|
Problema | Invers modular | Scor | 50 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.47 kb |
#include <fstream>
#define UI unsigned int
using namespace std;
ifstream f("inversmodular.in"); ofstream g("inversmodular.out");
UI a, b, n, ai, s, t, s1, s2, t1, t2, q, r, k;
int main()
{f>>a>>n; b=n, q=a/b; r=a%b;
s1=1; t1=0; s2=0; t2=1;
while(r)
{s=s1-q*s2; s1=s2; s2=s;
t=t1-q*t2; t1=t2; t2=t;
a=b, b=r; q=a/b; r=a%b;
}
if(s>0) g<<s<<'\n';
else {k=(-s)/n; r=(-s)%n;
if(r) k++;
g<<s+k*n<<'\n';
}
return 0;
}