z2.2.cpp

#include <iostream>
using namespace std;

int mod5(int x)
{
    return (x % 5 + 5) % 5;
}

int inv5(int x)
{
    // Поиск обратного элемента к x (mod 5)
    // x * inv = 1 (mod 5)
    x = mod5(x);
    for (int i = 1; i < 5; i++)
    {
        if ((x * i) % 5 == 1) return i;
    }
    return -1; // если не нашли
}

bool isSquareMod5(int x)
{
    x = mod5(x);
    for (int r = 0; r < 5; r++)
        if (mod5(r*r) == x) return true;
    return false;
}

int sqrtMod5(int x)
{
    x = mod5(x);
    for (int r = 0; r < 5; r++)
        if (mod5(r*r) == x) return r;
    return -1;
}

// Функция factorQuadratic: раскладывает ax^2 + bx + c (mod 5)
// Возвращает строку вида: "Не раскладывается" или "(x - r1)(x - r2)"
string factorQuadratic(int a, int b, int c)
{
    a = mod5(a);
    b = mod5(b);
    c = mod5(c);

    if (a == 0)
    {
        // Линейный случай
        if (b == 0)
        {
            if (c == 0) return "0 = 0, любой x";
            else        return "Нет решений";
        }
        int ib = inv5(b);
        if (ib == -1) return "Нет решений (b=0 в F5)";
        int root = mod5(-c * ib);
        return "Линейно: (x - " + to_string(root) + ")";
    }

    int D = mod5(b*b - 4*a*c);
    if (!isSquareMod5(D)) return "Неприводим над F5";

    int sd = sqrtMod5(D);
    int i2a = inv5(mod5(2*a));
    if (i2a == -1) return "Обратный элемент к 2a не найден";

    // Первый корень
    int r1 = mod5( mod5(-b + sd) * i2a );
    // Второй корень
    int r2 = mod5( mod5(-b - sd) * i2a );

    if (r1 == r2)
    {
        return "(x - " + to_string(r1) + ")^2";
    }
    else
    {
        return "(x - " + to_string(r1) + ")(x - " + to_string(r2) + ")";
    }
}

int main()
{
    int a, b, c;
    cout << "Введите a, b, c в F5: ";
    cin >> a >> b >> c;
    string result = factorQuadratic(a, b, c);
    cout << result << endl;
    return 0;
}