Расширенный алгоритм Евклида. X постоянно равно нулю - C#
Формулировка задачи:
возникает проблема, X в итоге постоянно равен нулю, чего быть не должно
namespace evklid
{
class Program
{
static void Main(string[] args)
{
int a = Convert.ToInt32(Console.ReadLine());
int m = Convert.ToInt32(Console.ReadLine());
int x = 0, d = 1;
while (a>0)
{
int q = m / (a);
int y = a;
a = m % (a);
m = y;
y = d;
d = x - (q * (d));
x = y;
}
x = x % m;
if (x<0)
{
x = (x + m) % m;
}
}
}
}Решение задачи: «Расширенный алгоритм Евклида. X постоянно равно нулю»
textual
Листинг программы
int a = Convert.ToInt32(Console.ReadLine());
int m = Convert.ToInt32(Console.ReadLine());
int i = m, v = 0, d = 1;
while (a > 0)
{
int t = i / a, x = a;
a = i % x;
i = x;
x = d;
d = v - t * x;
v = x;
}
v %= m;
if (v < 0) v = (v + m) % m;