kroneker

#include <iostream>
#include <set>
#include <vector>
#include <utility>
#include <iterator>
#include <limits>
#include <typeinfo>
#include <functional>
#include <iostream>
#include <numeric>
#include <cmath>
#include <variant>
#include <ranges>
#include <vector>
#include <list>
#include <string>
#include <vector>
#include "src/Polynomial.cpp"
#include <iomanip>
#include <iostream>
#include <string>
#include <string_view>
#include <type_traits>
#define INT_SIZE 128
#define INFINTY std::numeric_limits<int>::max()

using basis_coefficients = std::vector<std::pair<float, float>>;
using basis_polynomials = std::vector<std::vector<float>>;
using coefs = std::vector<float>;
using binomial_coefs = std::pair<float, float>;
using namespace std;


variant<bool, basis_polynomials> get_coefficients(float _pl, coefs _xi)
{
    if(_xi.size() != set(_xi.begin(), _xi.end()).size())
        return false;
    float n = _xi.size();
    // for(int i = 0; i < _xi.size(); ++i){
    //     cout << _xi[i] << ' ';
    // }
    // cout << '\n';
    basis_polynomials coefficients(n, coefs(2));
    for (float i = 0; i < n; ++i)
    {
        if (i == _pl)
        {
            coefficients[i][0] = INFINTY;
            coefficients[i][1] = INFINTY;
        }
        else
        {
            if(_xi[_pl] - _xi[i] == 0){
                for(int j = 0; j < _xi.size(); ++j){
                    cout << _xi[j] << ' ';
                }
                cout << '\n';
            }
            coefficients[i][0] = 1 / (_xi[_pl] - _xi[i]);
            coefficients[i][1] = -_xi[i] / (_xi[_pl] - _xi[i]);
        }
    }
    basis_polynomials filtered_coefficients(n - 1, coefs(2));
    float j = 0;
    for (float i = 0; i < n; ++i)
    {
        if (coefficients[i][0] != INFINTY)
        {
            filtered_coefficients[j][0] = coefficients[i][1];
            filtered_coefficients[j][1] = coefficients[i][0];
            j++;
        }
    }
    return filtered_coefficients;
}

// coefs polynomialTimesPolynomial(coefs x, coefs y)
// {
//     float n = x.size() + y.size() - 1;
//     coefs result(n, float(0));
//     for (float i = 0; i < x.size(); ++i)
//     {
//         for (float j = 0; j < y.size(); ++j)
//         {
//             result[i + j] += x[i] * y[j];
//         }
//     }
//     return result;
// }

// coefs calculateBasisLagrangePolynomial(basis_polynomials filtered_coefs)
// {
//     float n = filtered_coefs.size();
//     coefs result(n + 1, float(0));
//     coefs tmp;
//     if (n == 1)
//         tmp = filtered_coefs[0];
//     else
//         tmp = polynomialTimesPolynomial(filtered_coefs[0], filtered_coefs[1]);
//     for (float i = 0; i < tmp.size(); ++i)
//         result[i] = tmp[i];
//     for (float i = 2; i < filtered_coefs.size(); ++i)
//     {
//         coefs tmp = polynomialTimesPolynomial(result, filtered_coefs[i]);
//         for (float j = 0; j < tmp.size(); ++j)
//             result[j] = tmp[j];
//     }
//     return result;
// }

// basis_polynomials calculateAllBasisLagrangePolynomial(coefs x)
// {
//     float n = x.size();
//     basis_polynomials result;
//     for (float pl = 0; pl < n; ++pl)
//         result.push_back(calculateBasisLagrangePolynomial(get_coefficients(pl, x)));
//     return result;
// }

variant<bool, basis_polynomials> get_polynomial_l(coefs _xi)
{
    variant<bool, vector<vector<int>>> ans;
    int n = _xi.size();
    basis_polynomials pli(n, coefs(n));
    for (float pl = 0; pl < n; ++pl)
    {
        variant<bool, basis_polynomials> check = get_coefficients(pl, _xi);
        if(holds_alternative<bool>(check))
            return false;
        basis_polynomials coefficients = get<basis_polynomials>(check);
        for (float i = 1; i < n - 1; ++i)
        {
            if (i == 1)
            {
                pli[pl][0] = coefficients[i - 1][0] * coefficients[i][0];
                pli[pl][1] = coefficients[i - 1][1] * coefficients[i][0] + coefficients[i][1] * coefficients[i - 1][0];
                pli[pl][2] = coefficients[i - 1][1] * coefficients[i][1];
            }
            else
            {
                coefs clone_pli(n, float(0));
                for (float val = 0; val < n; ++val)
                    clone_pli[val] = pli[pl][val];
                coefs zeros_pli(n, float(0));
                float product_1;
                float product_2;
                for (float j = 0; j < n - 1; j++)
                {
                    product_1 = clone_pli[j] * coefficients[i][0];
                    product_2 = clone_pli[j] * coefficients[i][1];
                    zeros_pli[j] += product_1;
                    zeros_pli[j + 1] += product_2;
                }
                for (float val = 0; val < n; ++val)
                    pli[pl][val] = zeros_pli[val];
            }
        }
    }
    cout << pli.size() << '\n';
    for(int i = 0; i < pli.size(); ++i){
        for(int j = 0; j < pli[i].size(); ++j){
            cout << pli[i][j] << ", ";
        }
        cout << " | ";
    }
    cout << "-> ";
    // vector<vector<int>> res;
    // int check = pli[0].size();
    // for(size_t i = 0; i < pli.size(); ++i){
    //     vector<int> tmp_vec;
    //     for(size_t j = 0; j < pli[i].size(); ++j){
            // float integerPart;
            // float fractionalPart = modf(pli[i][j], &integerPart);
    //         if(fractionalPart == 0.0){
    //             // cout << "int " <<integerPart << '\n';
    //             int tmp = static_cast<int>(integerPart);
    //             // res[i][j] = tmp;
    //             tmp_vec.push_back(tmp);
    //         }
    //         if(tmp_vec.size() == check){
    //             return false;
    //         }
    //     }
    // }
    // for(int i = 0; i < res.size(); ++i){
    //     for(int j = 0; j < res[i].size(); ++j){
    //         cout << res[i][j] << ' ';
    //     }
    //     cout << '\n';
    // }
    // if(res.size() == 0)
    //     return false;
    return pli;
}

using int_coefs = vector<vector<int>>;
variant<bool, Polynomial<int>> get_polynomial(coefs xi, coefs _yi)
{
    variant<bool, Polynomial<int>> ans;
    float n = xi.size();
    basis_polynomials polynomial_l;
    bool bres;
    variant<bool, basis_polynomials> check = get_polynomial_l(xi);
    if(holds_alternative<bool>(check)){
        bres = get<bool>(check);
        return false;
    }
    polynomial_l = get<basis_polynomials>(check);
    for (float i = 0; i < n; ++i)
    {
        for (float j = 0; j < n; ++j)
            polynomial_l[i][j] *= _yi[i];
    }
    vector<float> Lagrange(n, float(0));
    for (float i = 0; i < n; ++i)
    {
        for (float j = 0; j < n; ++j)
            Lagrange[i] += polynomial_l[j][i];
    }
    for(int i = 0; i < Lagrange.size(); ++i){
        cout << Lagrange[i] << ' ';
    }
    cout << '\n';
    vector<int> res;
    for(size_t i = 0; i < Lagrange.size(); ++i){
        float integerPart;
        float fractionalPart = modf(Lagrange[i], &integerPart);
        if(fractionalPart == 0.0){
            res.push_back(static_cast<int>(Lagrange[i]));
        } else{
            return false;
        }
    }
    // Polynomial<int> res = Polynomial<int>(Lagrange);
    return Polynomial<int> {res};
}

bool IsPrime(const int n)
{
    for (int i = 2; i * i <= n; i++)
        if (n % i == 0)
            return false;
    return n > 1;
}

set<int> toPrimeNumbers(int num)
{
    num = abs(num);
    set<int> nums;
    if (num == 0)
    {
        return nums;
    }
    if (IsPrime(num))
    {
        nums.insert(num);
        return nums;
    }
    nums.insert(num);
    nums.insert(1);
    for (size_t i = 2; i * i <= num; ++i)
    {
        if (num % i == 0 && IsPrime(i))
        {
            nums.insert(i);
            nums.insert(num / i);
        }
    }
    return nums;
}

int gcd_n(const std::vector<int>& values) {
   if (values.empty())
       return -1;
   if (values.size() == 1)
       return values[0];
   int gcd_value = gcd(values[0], values[1]);
   for (int i = 2; i < values.size(); ++i) {
       gcd_value = gcd(gcd_value, values[i]);
   }
   return gcd_value;
}

pair<int, Polynomial<int>> ContPrim(Polynomial<int> f) {
    if (f == 0) {
        return make_pair(NULL, NULL);
    } else {
        // Get the coefficients of the polynomial
        vector<int> cl = f.get_coef();

        // Compute the greatest common divisor of the coefficients
        int cf = gcd_n(cl);

        for(size_t i = 0; i <= f.Degree(); ++i){
            cl[i] /= cf;
        }

        f.set_coef(cl);

        return make_pair(cf, f);
    }
}

set<pair<int, int>> CartesianS(set<int> A, set<int> B)
{
    set<pair<int, int>> AxB;

    for (int a : A)
    {
        for (int b : B)
        {
            AxB.insert(make_pair(a, b));
        }
    }

    return AxB;
}

vector<vector<int>> CartesianSL(set<vector<int>> A, set<vector<int>> B)
{
    vector<vector<int>> AxB;

    for (const vector<int> &a : A)
    {
        for (const vector<int> &b : B)
        {
            AxB.push_back(vector<int>(a.begin(), a.end()));
            AxB.back().insert(AxB.back().end(), b.begin(), b.end());
        }
    }

    return AxB;
}

set<vector<int>> SetOfLists(set<int> A)
{
    set<vector<int>> B;

    for (int a : A)
    {
        B.insert({a});
    }

    return B;
}

set<vector<int>> CartesianLS(vector<set<int>> U)
{
    int n = U.size();

    if (n == 0)
    {
        return {};
    }

    int N = 1;
    vector<set<vector<int>>> V(n);
    for (int i = 0; i < n; i++)
    {
        N *= U[i].size();
        V[i] = SetOfLists(U[i]);
    }

    if (N == 0)
    {
        return {};
    }

    set<vector<int>> P = V[0];
    for (int i = 1; i < n; i++)
    {
        set<vector<int>> temp;
        for (const vector<int> &p : P)
        {
            for (const vector<int> &v : V[i])
            {
                vector<int> new_p = p;
                new_p.insert(new_p.end(), v.begin(), v.end());
                temp.insert(new_p);
            }
        }
        P = temp;
    }

    return P;
}

// vector<int> DIV(vector<int> coefficients) {
//     while (coefficients.back() == 0) {
//         coefficients.pop_back();
//     }
//     return coefficients;
// }

// vector<int> QUO(vector<int> dividend, vector<int> divisor) {
//     int div_size = divisor.size();
//     int dif = dividend.size() - div_size + 1;
//     for (int i = 0; i < dif; i++) {
//         int coef = dividend[i] / divisor[0];
//         for (int j = 0; j < div_size; j++) {
//             dividend[i + j] -= coef * divisor[j];
//         }
//     }
//     return DIV(dividend);
// }

void printVector(const vector<int> &v)
{
    cout << "[";
    for (int i = 0; i < v.size(); ++i)
    {
        cout << v[i];
        if (i != v.size() - 1)
        {
            cout << ", ";
        }
    }
    cout << "]";
}

void printSet(const set<int> &A)
{
    copy(A.begin(), A.end(), ostream_iterator<int>(cout, " "));
}

struct Kroneker{
    int cf;
    Polynomial<int> prf;
    bool driven;
    Polynomial<int> x_a;
    Polynomial<int> quo;
};

int get_func_val(Polynomial<int> f, int xi){
    int res = f[0];
    for(size_t i = 1; i <= f.Degree(); ++i){
        res += f[i] * pow(xi, i);
    }
    return res;
}

struct Kroneker kroneker(Polynomial<int> f){
    int n = f.Degree();
    struct Kroneker ans;
    if(n == 0){
        ans.cf = abs(f[0]);
        return ans;
    }
    pair<int, Polynomial<int>> tmp = ContPrim(f);
    ans.cf = tmp.first;
    ans.prf = tmp.second;
    int m = n / 2;
    vector<int> x(m, 0);
    vector<int> y(m, 0);
    vector<set<int>> DY;
    for(size_t i = 0; i <= m; ++i){
        x[i] = i;
        y[i] = get_func_val(ans.prf, i);
        if(y[i] == 0){
            Polynomial<int> x_a{{-x[i], 1}};
            Polynomial<int> quo = (ans.prf / x_a).first; // возращается пара, возможен нецелочисленное деление
            ans.driven = false;
            ans.x_a = x_a;
            ans.quo = quo;
            return ans;
        }
        DY.push_back(toPrimeNumbers(y[i]));
    }
    set<vector<int>> M = CartesianLS(DY);
    vector<vector<float>> f_values;
    vector<vector<float>> vec_M;
    for(const auto& mu : M){
        vector<float> mu_values;
        vector<float> args;
        for(const auto& mu_elem : mu){
            mu_values.push_back(static_cast<float>(get_func_val(ans.prf, mu_elem)));
            args.push_back(static_cast<float>(mu_elem));
        }
        f_values.push_back(mu_values);
        vec_M.push_back(args);
    }
    for(size_t i = 0; i < vec_M.size(); ++i){
        variant<bool, Polynomial<int>> g = get_polynomial(vec_M[i], f_values[i]);
        if(holds_alternative<Polynomial<int>>(g)){
            // cout << "here" << '\n';
            Polynomial<int> h = get<Polynomial<int>>(g);
            // cout << h << '\n';
            pair<Polynomial<int>, int> tmp_rem = ans.prf / h;
            Polynomial<int> rem = ans.prf % h;
            if(h.Degree() >= 1 && rem[0] == 0 && rem.Degree() == -1 && tmp_rem.second == 1){
                if(h[h.Degree()] < 0){
                    h *= -1;
                }
                ans.driven = false;
                ans.x_a = h;
                ans.quo = tmp_rem.first;
                return ans;
            }
        }
    }
    ans.driven = true;
    return ans;
}

int main0()
{
    vector<set<int>> U = {{1, 2}, {3, 4, 5, 7}, {8, 9}}; // Пример списка множеств U

    set<vector<int>> result = CartesianLS(U);
    cout << "Cartesian product of U: ";
    for (const vector<int> &list : result)
    {
        printVector(list);
        cout << " ";
    }
    cout << endl;

    return 0;
}

int main1()
{
    set<int> A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; // Пример множества A

    set<vector<int>> result = SetOfLists(A);
    cout << "Set of lists B: ";
    for (const vector<int> &list : result)
    {
        printVector(list);
        cout << " ";
    }
    cout << endl;

    return 0;
}

int main2()
{
    set<vector<int>> A = {{1}, {2}, {4}};                  // Пример множества A
    set<vector<int>> B = {{1, 1}, {1, 2}, {2, 1}, {2, 2}}; // Пример множества B

    vector<vector<int>> result = CartesianSL(A, B);
    cout << "Cartesian product of A and B: ";
    for (const vector<int> &pair : result)
    {
        printVector(pair);
        cout << " ";
    }
    cout << endl;

    return 0;
}

int main3()
{
    set<int> B = {1, 2, 3}; // Пример множества A
    set<int> A = {4, 5};    // Пример множества B

    set<pair<int, int>> result = CartesianS(A, B);
    cout << "Cartesian product of A and B: ";
    for (auto it = result.begin(); it != result.end(); ++it)
    {
        cout << "(" << it->first << ", " << it->second << ") ";
    }
    cout << endl;

    return 0;
}

int main4()
{
    set<int> A;
    int a = -12;
    printSet(toPrimeNumbers(a));
    return 0;
}

int main(){
    Polynomial<int> f({8, 0, 0, 0, 2});
    Kroneker tmp = kroneker(f);
    cout << tmp.cf << '\n';
    cout << tmp.prf << '\n';
    cout << tmp.driven << '\n';
    cout << tmp.x_a << '\n';
    cout << tmp.quo << '\n';
    return 0;
}