Требуются решения предыдущих двух задач. Википедия.
#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 ) {
while (y < 1) y += n;
return y;
}
else {
return 0;
}
}
int china_N(unsigned int a1, unsigned int a2, unsigned int r1, unsigned int r2)
{
unsigned int M = a1 * a2;
unsigned int M1 = M / a1;
unsigned int M2 = M / a2;
int RM1 = rev_mod(a1, M1);
int RM2 = rev_mod(a2, M2);
int X1 = r1 * M1 *RM1;
int X2 = r2 * M2 *RM2;
int X = (X1 + X2) % M;
return X;
}
int _tmain(int argc, _TCHAR* argv[])
{
unsigned int n, m, a, b;
cin >> n;
cin >> m;
cin >> a;
cin >> b;
cout << endl << china_N(n, m, a, b) << endl;
system("pause");
return 0;
}