Здравствуйте!!! Написал прогу для решения сравнения по модулю ax=b(mod m), где (a,m)=1(взаимно простые числа), работает правильно.
но как быть когда (a,m)>1? Например: 6x=51(mod 105) имеет три решения: x=(26,61,96)(mod 105), как это сделать?
| Код |
#include "stdafx.h"
#include <iostream>
#include <cmath>
using namespace std;
int solveCongruences(int A[], int B[], int M[], int n)
{
int x = 0, mod = 1;
for (int i = 0; i < n; i++)
{ int r1 = A[i]*mod, r2 = M[i], x1 = 1, x2 = 0, r = 1;
while (r != 0)
{ int q = (int)floor((double)r1/r2), t = x1-q*x2;
x1 = x2; x2 = t; r = r1-q*r2; r1 = r2; r2 = r;
}
int b = B[i]-A[i]*x;
if (b % r1 != 0){ cout << "Не имеет решений"; return 0; }
x += mod * b * x1/r1;
mod *= M[i]/r1;
}
if (x < 0 || x >= mod) x -= mod * (int)floor((double)x/mod);
cout << "x = " << x << " (mod " << mod << ")";
return 0;
}
int main()
{
setlocale(0,"rus");
int A[] = {6}, B[] = {1}, M[] = {10}, n = 1;
cout << "Решение " << (n==1 ? "сравнения" : "системы сравнений")
<< " по модулю:\n\n";
for (int i = 0; i < n; i++)
{ cout << " " << A[i] << "x = " << B[i] << " (mod " << M[i] << ")\n"; }
cout << "\nОтвет: ";
solveCongruences(A, B, M, n);
system("pause > null");
return 0;
}
|
|
)