z12.3.cpp

#include <iostream>
#include "string.h"
#include "array.h"
using namespace std;

// Возвращаем степень полинома (индекс старшего ненулевого бита)
int degree(unsigned int poly)
{
    if (poly == 0) return -1;
    // built-in GCC: __builtin_clz(x) кол-во ведущих нулей
    // степень = 31 - clz
    return 31 - __builtin_clz(poly);
}

// Остаток от деления A на B (полиномы над F2)
unsigned int polyMod(unsigned int A, unsigned int B)
{
    while (A != 0 && degree(A) >= degree(B))
    {
        int shift = degree(A) - degree(B);
        A ^= (B << shift); // XOR
    }
    return A;
}

bool isIrreducible(unsigned int poly, int n)
{
    if (degree(poly) != n) return false;
    for (int d = 1; d < n; d++)
    {
        // перебираем все полиномы степени d
        unsigned int start = 1u << d;
        unsigned int end   = (1u << (d+1)) - 1;
        for (unsigned int test = start; test <= end; test++)
        {
            if (polyMod(poly, test) == 0)
                return false;
        }
    }
    return true;
}

int main()
{
    cout << "Введите n (<= 8 примерно): ";
    int n;
    cin >> n;

    unsigned int start = 1u << n;
    unsigned int end   = (1u << (n+1)) - 1;

    Array<unsigned int> irreducibles;
    for (unsigned int poly = start; poly <= end; poly++)
    {
        if (isIrreducible(poly, n))
        {
            irreducibles.append(poly);
        }
    }

    // Выводим, используя String
    for (int i = 0; i < irreducibles.size(); i++)
    {
        unsigned int p = irreducibles[i];
        String msg = "P: ";
        // Построим двоичную строку
        for (int b = n; b >= 0; b--)
        {
            char c = ((p >> b) & 1) + '0';
            msg = msg + c;
        }
        msg = msg + " (неприводим)";
        cout << msg << endl;
    }

    cout << "Всего неприводимых: " << irreducibles.size() << endl;

    return 0;
}