Требуется решение предыдущей задачи!
В помощь: Википедия. Да, с первого взгляда это совсем не та статья, но для решения этой задачи придется ее прочитать и усвоить.
#include "stdafx.h"
#include <iostream>
using namespace std;
unsigned int NOD_euqlid_ext(unsigned int a, unsigned int b, int& x, int& y)
{
int x2 = 1, x1 = 0;
int y2 = 0, y1 = 1;
unsigned int q, r;
while (b > 0) {
q = a / b;
r = a - b * q;
x = x2 - q * x1;
y = y2 - q * y1;
a = b;
b = r;
x2 = x1;
x1 = x;
y2 = y1;
y1 = y;
}
x = x2;
y = y2;
return a;
}
int rev_mod(unsigned int n, unsigned int a)
{
unsigned int d;
int x, y;
d = NOD_euqlid_ext(n, a, x, y);
if (d = 1 ) {
return y;
}
else {
return 0;
}
}
int _tmain(int argc, _TCHAR* argv[])
{
unsigned int a, n, d;
cin >> n;
cin >> a;
cout << endl << rev_mod(n, a) << endl;
system("pause");
return 0;
}