API tools faq
paste
Advertisement
maxim_shlyahtin

kroneker2

maxim_shlyahtin
Dec 20th, 2023 (edited)
681
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 24.38 KB | None | 0 0
raw download clone embed print report
  1. #include <iostream>
  2. #include <set>
  3. #include <vector>
  4. #include <utility>
  5. #include <iterator>
  6. #include <limits>
  7. #include <numeric>
  8. #include <cmath>
  9. #include <variant>
  10. #include <string>
  11. // #include "src/Polynomial.cpp"
  12. #include <boost/math/tools/polynomial.hpp>
  13. // #include <iomanip>
  14. // #include <iostream>
  15. // #include <string>
  16. // #include <string_view>
  17. // #include <type_traits>
  18. #define INT_SIZE 128
  19. #define INFINTY std::numeric_limits<int>::max()
  20.  
  21. using basis_coefficients = std::vector<std::pair<double, double>>;
  22. using basis_polynomials = std::vector<std::vector<double>>;
  23. using coefs = std::vector<double>;
  24. using binomial_coefs = std::pair<double, double>;
  25. using namespace std;
  26.  
  27. using namespace boost::math;
  28. using namespace boost::math::tools; // for polynomial
  29. using boost::lexical_cast;
  30.  
  31. // variant<bool, basis_polynomials> get_coefficients(double _pl, coefs _xi)
  32. // {  
  33. //     if(_xi.size() != set(_xi.begin(), _xi.end()).size())
  34. //         return false;
  35. //     double n = _xi.size();
  36. //     // for(int i = 0; i < _xi.size(); ++i){
  37. //     //     cout << _xi[i] << ' ';
  38. //     // }
  39. //     // cout << '\n';
  40. //     basis_polynomials coefficients(n, coefs(2));
  41. //     for (double i = 0; i < n; ++i)
  42. //     {
  43. //         if (i == _pl)
  44. //         {  
  45. //             coefficients[i][0] = INFINTY;
  46. //             coefficients[i][1] = INFINTY;
  47. //         }
  48. //         else
  49. //         {  
  50. //             if(_xi[_pl] - _xi[i] == 0){
  51. //                 for(int j = 0; j < _xi.size(); ++j){
  52. //                     cout << _xi[j] << ' ';
  53. //                 }
  54. //                 cout << '\n';
  55. //             }
  56. //             coefficients[i][0] = 1 / (_xi[_pl] - _xi[i]);
  57. //             coefficients[i][1] = -_xi[i] / (_xi[_pl] - _xi[i]);
  58. //         }
  59. //     }
  60. //     basis_polynomials filtered_coefficients(n - 1, coefs(2));
  61. //     double j = 0;
  62. //     for (double i = 0; i < n; ++i)
  63. //     {
  64. //         if (coefficients[i][0] != INFINTY)
  65. //         {
  66. //             filtered_coefficients[j][0] = coefficients[i][1];
  67. //             filtered_coefficients[j][1] = coefficients[i][0];
  68. //             j++;
  69. //         }
  70. //     }
  71. //     return filtered_coefficients;
  72. // }
  73.  
  74. // // coefs polynomialTimesPolynomial(coefs x, coefs y)
  75. // // {
  76. // //     double n = x.size() + y.size() - 1;
  77. // //     coefs result(n, double(0));
  78. // //     for (double i = 0; i < x.size(); ++i)
  79. // //     {
  80. // //         for (double j = 0; j < y.size(); ++j)
  81. // //         {
  82. // //             result[i + j] += x[i] * y[j];
  83. // //         }
  84. // //     }
  85. // //     return result;
  86. // // }
  87.  
  88. // // coefs calculateBasisLagrangePolynomial(basis_polynomials filtered_coefs)
  89. // // {
  90. // //     double n = filtered_coefs.size();
  91. // //     coefs result(n + 1, double(0));
  92. // //     coefs tmp;
  93. // //     if (n == 1)
  94. // //         tmp = filtered_coefs[0];
  95. // //     else
  96. // //         tmp = polynomialTimesPolynomial(filtered_coefs[0], filtered_coefs[1]);
  97. // //     for (double i = 0; i < tmp.size(); ++i)
  98. // //         result[i] = tmp[i];
  99. // //     for (double i = 2; i < filtered_coefs.size(); ++i)
  100. // //     {
  101. // //         coefs tmp = polynomialTimesPolynomial(result, filtered_coefs[i]);
  102. // //         for (double j = 0; j < tmp.size(); ++j)
  103. // //             result[j] = tmp[j];
  104. // //     }
  105. // //     return result;
  106. // // }
  107.  
  108. // // basis_polynomials calculateAllBasisLagrangePolynomial(coefs x)
  109. // // {
  110. // //     double n = x.size();
  111. // //     basis_polynomials result;
  112. // //     for (double pl = 0; pl < n; ++pl)
  113. // //         result.push_back(calculateBasisLagrangePolynomial(get_coefficients(pl, x)));
  114. // //     return result;
  115. // // }
  116.  
  117. // variant<bool, basis_polynomials> get_polynomial_l(coefs _xi)
  118. // {  
  119. //     variant<bool, vector<vector<int>>> ans;
  120. //     int n = _xi.size();
  121. //     basis_polynomials pli(n, coefs(n));
  122. //     for (double pl = 0; pl < n; ++pl)
  123. //     {  
  124. //         variant<bool, basis_polynomials> check = get_coefficients(pl, _xi);
  125. //         if(holds_alternative<bool>(check))
  126. //             return false;
  127. //         basis_polynomials coefficients = get<basis_polynomials>(check);
  128. //         for (double i = 1; i < n - 1; ++i)
  129. //         {
  130. //             if (i == 1)
  131. //             {
  132. //                 pli[pl][0] = coefficients[i - 1][0] * coefficients[i][0];
  133. //                 pli[pl][1] = coefficients[i - 1][1] * coefficients[i][0] + coefficients[i][1] * coefficients[i - 1][0];
  134. //                 pli[pl][2] = coefficients[i - 1][1] * coefficients[i][1];
  135. //             }
  136. //             else
  137. //             {
  138. //                 coefs clone_pli(n, double(0));
  139. //                 for (double val = 0; val < n; ++val)
  140. //                     clone_pli[val] = pli[pl][val];
  141. //                 coefs zeros_pli(n, double(0));
  142. //                 double product_1;
  143. //                 double product_2;
  144. //                 for (double j = 0; j < n - 1; j++)
  145. //                 {
  146. //                     product_1 = clone_pli[j] * coefficients[i][0];
  147. //                     product_2 = clone_pli[j] * coefficients[i][1];
  148. //                     zeros_pli[j] += product_1;
  149. //                     zeros_pli[j + 1] += product_2;
  150. //                 }
  151. //                 for (double val = 0; val < n; ++val)
  152. //                     pli[pl][val] = zeros_pli[val];
  153. //             }
  154. //         }
  155. //     }
  156. //     cout << pli.size() << '\n';
  157. //     for(int i = 0; i < pli.size(); ++i){
  158. //         for(int j = 0; j < pli[i].size(); ++j){
  159. //             cout << pli[i][j] << ", ";
  160. //         }
  161. //         cout << " | ";
  162. //     }
  163. //     cout << "-> ";
  164. //     // vector<vector<int>> res;
  165. //     // int check = pli[0].size();
  166. //     // for(size_t i = 0; i < pli.size(); ++i){
  167. //     //     vector<int> tmp_vec;
  168. //     //     for(size_t j = 0; j < pli[i].size(); ++j){
  169. //             // double integerPart;
  170. //             // double fractionalPart = modf(pli[i][j], &integerPart);
  171. //     //         if(fractionalPart == 0.0){
  172. //     //             // cout << "int " <<integerPart << '\n';
  173. //     //             int tmp = static_cast<int>(integerPart);
  174. //     //             // res[i][j] = tmp;
  175. //     //             tmp_vec.push_back(tmp);
  176. //     //         }
  177. //     //         if(tmp_vec.size() == check){
  178. //     //             return false;
  179. //     //         }
  180. //     //     }
  181. //     // }
  182. //     // for(int i = 0; i < res.size(); ++i){
  183. //     //     for(int j = 0; j < res[i].size(); ++j){
  184. //     //         cout << res[i][j] << ' ';
  185. //     //     }
  186. //     //     cout << '\n';
  187. //     // }
  188. //     // if(res.size() == 0)
  189. //     //     return false;
  190. //     return pli;
  191. // }
  192.  
  193. // using int_coefs = vector<vector<int>>;
  194. // variant<bool, polynomial<int>> get_polynomial(coefs xi, coefs _yi)
  195. // {  
  196. //     variant<bool, polynomial<int>> ans;
  197. //     double n = xi.size();
  198. //     basis_polynomials polynomial_l;
  199. //     bool bres;
  200. //     variant<bool, basis_polynomials> check = get_polynomial_l(xi);
  201. //     if(holds_alternative<bool>(check)){
  202. //         bres = get<bool>(check);
  203. //         return false;
  204. //     }
  205. //     polynomial_l = get<basis_polynomials>(check);
  206. //     for (double i = 0; i < n; ++i)
  207. //     {
  208. //         for (double j = 0; j < n; ++j)
  209. //             polynomial_l[i][j] *= _yi[i];
  210. //     }
  211. //     vector<double> Lagrange(n, double(0));
  212. //     for (double i = 0; i < n; ++i)
  213. //     {
  214. //         for (double j = 0; j < n; ++j)
  215. //             Lagrange[i] += polynomial_l[j][i];
  216. //     }
  217. //     for(int i = 0; i < Lagrange.size(); ++i){
  218. //         cout << Lagrange[i] << ' ';
  219. //     }
  220. //     cout << '\n';
  221. //     vector<int> res;
  222. //     for(size_t i = 0; i < Lagrange.size(); ++i){
  223. //         double integerPart;
  224. //         double fractionalPart = modf(Lagrange[i], &integerPart);
  225. //         if(fractionalPart == 0.0){
  226. //             res.push_back(static_cast<int>(Lagrange[i]));
  227. //         } else{
  228. //             return false;
  229. //         }
  230. //     }
  231. //     // polynomial<int> res = polynomial<int>(Lagrange);
  232. //     return polynomial<int> {res};
  233. // }
  234. basis_polynomials get_coefficients(double _pl, coefs _xi){
  235.     double n = _xi.size();
  236.     basis_polynomials coefficients(n, coefs(2));
  237.     for(double i = 0; i < n; ++i){
  238.         if (i == _pl){
  239.             coefficients[i][0] = INFINTY;
  240.             coefficients[i][1] = INFINTY;
  241.         } else {
  242.             coefficients[i][0] = 1 / (_xi[_pl] - _xi[i]);
  243.             coefficients[i][1] = -_xi[i] / (_xi[_pl] - _xi[i]);
  244.         }
  245.     }
  246.     basis_polynomials filtered_coefficients(n - 1, coefs(2));
  247.     double j = 0;
  248.     for(double i = 0; i < n; ++i){
  249.         if(coefficients[i][0] != INFINTY){
  250.             filtered_coefficients[j][0] = coefficients[i][1];
  251.             filtered_coefficients[j][1] = coefficients[i][0];
  252.             j++;
  253.         }
  254.     }
  255.     return filtered_coefficients;
  256. }
  257.  
  258. coefs polynomialTimesPolynomial(coefs x, coefs y){
  259.     double n = x.size() + y.size() - 1;
  260.     coefs result(n, double(0));
  261.     for(double i = 0; i < x.size(); ++i){
  262.         for(double j = 0; j < y.size(); ++j){
  263.             result[i + j] += x[i] * y[j];
  264.         }
  265.     }
  266.     return result;
  267. }
  268.  
  269. coefs calculateBasisLagrangePolynomial(basis_polynomials filtered_coefs){
  270.     double n = filtered_coefs.size();
  271.     coefs result(n + 1, double(0));
  272.     coefs tmp;
  273.     if(n == 1)
  274.         tmp = filtered_coefs[0];
  275.     else
  276.         tmp = polynomialTimesPolynomial(filtered_coefs[0], filtered_coefs[1]);
  277.     for(double i = 0; i < tmp.size(); ++i)
  278.         result[i] = tmp[i];
  279.     for(double i = 2; i < filtered_coefs.size(); ++i){
  280.         coefs tmp = polynomialTimesPolynomial(result, filtered_coefs[i]);
  281.         for(double j = 0; j < tmp.size(); ++j)
  282.             result[j] = tmp[j];
  283.     }
  284.     return result;
  285. }
  286.  
  287. basis_polynomials calculateAllBasisLagrangePolynomial(coefs x){
  288.     double n = x.size();
  289.     basis_polynomials result;
  290.     for(double pl = 0; pl < n; ++pl)
  291.         result.push_back(calculateBasisLagrangePolynomial(get_coefficients(pl, x)));
  292.     return result;
  293. }
  294.  
  295. basis_polynomials get_polynomial_l(coefs _xi){
  296.     double n = _xi.size();
  297.     basis_polynomials pli(n, coefs(n));
  298.     for(double pl = 0; pl < n; ++pl){
  299.         basis_polynomials coefficients = get_coefficients(pl, _xi);
  300.         for(double i = 1; i < n - 1; ++i){
  301.             if(i == 1){
  302.                 pli[pl][0] = coefficients[i - 1][0] * coefficients[i][0];
  303.                 pli[pl][1] = coefficients[i - 1][1] * coefficients[i][0] + coefficients[i][1] * coefficients[i - 1][0];
  304.                 pli[pl][2] = coefficients[i - 1][1] * coefficients[i][1];
  305.             } else{
  306.                 coefs clone_pli(n, double(0));
  307.                 for(double val = 0; val < n; ++val)
  308.                     clone_pli[val] = pli[pl][val];
  309.                 coefs zeros_pli(n, double(0));
  310.                 double product_1;
  311.                 double product_2;
  312.                 for(double j = 0; j < n - 1; j++){
  313.                     product_1 = clone_pli[j] * coefficients[i][0];
  314.                     product_2 = clone_pli[j] * coefficients[i][1];
  315.                     zeros_pli[j] += product_1;
  316.                     zeros_pli[j + 1] += product_2;
  317.                 }
  318.                 for(double val = 0; val < n; ++val)
  319.                     pli[pl][val] = zeros_pli[val];
  320.             }
  321.         }
  322.     }
  323.     return pli;
  324. }
  325.  
  326. coefs get_polynomial(coefs _xi, coefs _yi){
  327.     double n = _xi.size();
  328.     basis_polynomials polynomial_l = get_polynomial_l(_xi);
  329.     for(double i = 0; i < n; ++i){
  330.         for(double j = 0; j < n; ++j)
  331.             polynomial_l[i][j] *= _yi[i];
  332.     }
  333.     coefs Lagrange(n, double(0));
  334.     for(double i = 0; i < n; ++i){
  335.         for(double j = 0; j < n; ++j)
  336.             Lagrange[i] += polynomial_l[j][i];
  337.     }
  338.     return Lagrange;
  339. }
  340.  
  341. bool IsPrime(const int n)
  342. {
  343.     for (int i = 2; i * i <= n; i++)
  344.         if (n % i == 0)
  345.             return false;
  346.     return n > 1;
  347. }
  348.  
  349. set<int> toPrimeNumbers(int num)
  350. {
  351.     num = abs(num);
  352.     set<int> nums;
  353.     if (num == 0)
  354.     {
  355.         return nums;
  356.     }
  357.     if (IsPrime(num))
  358.     {
  359.         nums.insert(num);
  360.         return nums;
  361.     }
  362.     nums.insert(num);
  363.     nums.insert(1);
  364.     for (size_t i = 2; i * i <= num; ++i)
  365.     {
  366.         if (num % i == 0 && IsPrime(i))
  367.         {
  368.             nums.insert(i);
  369.             nums.insert(num / i);
  370.         }
  371.     }
  372.     return nums;
  373. }
  374.  
  375. int gcd_n(const std::vector<int>& val) {
  376.    if (val.empty())
  377.        return -1;
  378.    if (val.size() == 1)
  379.        return val[0];
  380.     vector<int> values;
  381.     for(int i = 0; i < val.size(); ++i){
  382.         if(val[i] != 0){
  383.             values.push_back(val[i]);
  384.         }
  385.     }
  386.    int gcd_value = gcd(values[0], values[1]);
  387.    for (int i = 2; i < values.size(); ++i) {
  388.        gcd_value = gcd(gcd_value, values[i]);
  389.    }
  390.    return gcd_value;
  391. }
  392.  
  393. pair<int, polynomial<int>> ContPrim(polynomial<int> f) {
  394.     if (f.data().at(0) == 0 && f.size() == 1) {
  395.         return make_pair(0, polynomial<int>({0}));
  396.     } else {
  397.         // Get the coefficients of the polynomial
  398.         vector<int> cl = f.data();
  399.  
  400.         // Compute the greatest common divisor of the coefficients
  401.         int cf = gcd_n(cl);
  402.  
  403.         for(size_t i = 0; i <= f.degree(); ++i){
  404.             cl[i] /= cf;
  405.         }
  406.  
  407.         f = polynomial<int>(cl);
  408.  
  409.         return make_pair(cf, f);
  410.     }
  411. }
  412.  
  413. set<pair<int, int>> CartesianS(set<int> A, set<int> B)
  414. {
  415.     set<pair<int, int>> AxB;
  416.  
  417.     for (int a : A)
  418.     {
  419.         for (int b : B)
  420.         {
  421.             AxB.insert(make_pair(a, b));
  422.         }
  423.     }
  424.  
  425.     return AxB;
  426. }
  427.  
  428. vector<vector<int>> CartesianSL(set<vector<int>> A, set<vector<int>> B)
  429. {
  430.     vector<vector<int>> AxB;
  431.  
  432.     for (const vector<int> &a : A)
  433.     {
  434.         for (const vector<int> &b : B)
  435.         {
  436.             AxB.push_back(vector<int>(a.begin(), a.end()));
  437.             AxB.back().insert(AxB.back().end(), b.begin(), b.end());
  438.         }
  439.     }
  440.  
  441.     return AxB;
  442. }
  443.  
  444. set<vector<int>> SetOfLists(set<int> A)
  445. {
  446.     set<vector<int>> B;
  447.  
  448.     for (int a : A)
  449.     {
  450.         B.insert({a});
  451.     }
  452.  
  453.     return B;
  454. }
  455.  
  456. set<vector<int>> CartesianLS(vector<set<int>> U)
  457. {
  458.     int n = U.size();
  459.  
  460.     if (n == 0)
  461.     {
  462.         return {};
  463.     }
  464.  
  465.     int N = 1;
  466.     vector<set<vector<int>>> V(n);
  467.     for (int i = 0; i < n; i++)
  468.     {
  469.         N *= U[i].size();
  470.         V[i] = SetOfLists(U[i]);
  471.     }
  472.  
  473.     if (N == 0)
  474.     {
  475.         return {};
  476.     }
  477.  
  478.     set<vector<int>> P = V[0];
  479.     for (int i = 1; i < n; i++)
  480.     {
  481.         set<vector<int>> temp;
  482.         for (const vector<int> &p : P)
  483.         {
  484.             for (const vector<int> &v : V[i])
  485.             {
  486.                 vector<int> new_p = p;
  487.                 new_p.insert(new_p.end(), v.begin(), v.end());
  488.                 temp.insert(new_p);
  489.             }
  490.         }
  491.         P = temp;
  492.     }
  493.  
  494.     return P;
  495. }
  496.  
  497. // vector<int> DIV(vector<int> coefficients) {
  498. //     while (coefficients.back() == 0) {
  499. //         coefficients.pop_back();
  500. //     }
  501. //     return coefficients;
  502. // }
  503.  
  504. // vector<int> QUO(vector<int> dividend, vector<int> divisor) {
  505. //     int div_size = divisor.size();
  506. //     int dif = dividend.size() - div_size + 1;
  507. //     for (int i = 0; i < dif; i++) {
  508. //         int coef = dividend[i] / divisor[0];
  509. //         for (int j = 0; j < div_size; j++) {
  510. //             dividend[i + j] -= coef * divisor[j];
  511. //         }
  512. //     }
  513. //     return DIV(dividend);
  514. // }
  515.  
  516. void printVector(const vector<int> &v)
  517. {
  518.     cout << "[";
  519.     for (int i = 0; i < v.size(); ++i)
  520.     {
  521.         cout << v[i];
  522.         if (i != v.size() - 1)
  523.         {
  524.             cout << ", ";
  525.         }
  526.     }
  527.     cout << "]";
  528. }
  529.  
  530. void printSet(const set<int> &A)
  531. {
  532.     copy(A.begin(), A.end(), ostream_iterator<int>(cout, " "));
  533. }
  534.  
  535. struct Kroneker{
  536.     int cf;
  537.     polynomial<int> prf;
  538.     bool driven;
  539.     polynomial<int> x_a;
  540.     polynomial<int> quo;
  541. };
  542.  
  543. set<int> divisors(int a) {
  544.     set<int> divisors;
  545.     if (a == 0) {
  546.         cout << "All integers divide zero!";
  547.         return divisors;
  548.     }
  549.     divisors.insert(-1);
  550.     divisors.insert(1);
  551.     divisors.insert(-a);
  552.     divisors.insert(a);
  553.     for (int k = 2; k <= floor(abs(a) / 2); ++k) {
  554.         if (a % k == 0) {
  555.             divisors.insert(a / k);
  556.             divisors.insert(-a / k);
  557.             divisors.insert(-k);
  558.             divisors.insert(k);
  559.         }
  560.     }
  561.     return divisors;
  562. }
  563.  
  564. int get_func_val(polynomial<int> f, int xi){
  565.     int res = f[0];
  566.     for(size_t i = 1; i <= f.degree(); ++i){
  567.         res += f[i] * pow(xi, i);
  568.     }
  569.     return res;
  570. }
  571.  
  572. variant<bool, polynomial<int>> type_check(coefs& f){
  573.     vector<int> res;
  574.     for(size_t i = 0; i < f.size(); ++i){
  575.         double integerPart;
  576.         double fractionalPart = modf(f[i], &integerPart);
  577.         if(fractionalPart == 0.0){
  578.             res.push_back(static_cast<int>(f[i]));
  579.         } else{
  580.             return false;
  581.         }
  582.     }
  583.     // polynomial<int> res = polynomial<int>(Lagrange);
  584.     return polynomial<int> {res};
  585. }
  586.  
  587.  
  588.  
  589. struct Kroneker kroneker(polynomial<int> f){
  590.     int n = f.degree();
  591.     struct Kroneker ans;
  592.     if(n == 0){
  593.         ans.cf = abs(f[0]);
  594.         return ans;
  595.     }
  596.     pair<int, polynomial<int>> tmp = ContPrim(f);
  597.     ans.cf = tmp.first;
  598.     ans.prf = tmp.second;
  599.     // cout << n << '\n';
  600.     int m = n / 2;
  601.     if(n <= 1){
  602.         ans.driven = true;
  603.         ans.x_a = ans.prf;
  604.         ans.quo = polynomial<int>(1);  
  605.         return ans;
  606.     }
  607.     vector<int> x(m, 0);
  608.     vector<int> y(m, 0);
  609.     vector<set<int>> DY;
  610.     for(size_t i = 0; i <= m; ++i){
  611.         x[i] = i;
  612.         y[i] = get_func_val(ans.prf, x[i]);
  613.         int tmp = get_func_val(ans.prf, -x[i]);
  614.         if(tmp == 0 || y[i] == 0){
  615.             polynomial<int> x_a = y[i] == 0 ? polynomial<int>({-x[i], 1}) : polynomial<int>({x[i], 1});
  616.             polynomial<int> quo = quotient_remainder(ans.prf, x_a).first; // возращается пара, возможен нецелочисленное деление
  617.             ans.driven = false;
  618.             // cout << quo << '\n';
  619.             ans.x_a = x_a;
  620.             ans.quo = quo;
  621.             return ans;
  622.         }
  623.         DY.push_back(divisors(y[i]));
  624.     }
  625.     set<vector<int>> M = CartesianLS(DY);
  626.     vector<vector<double>> f_values;
  627.     vector<vector<double>> vec_M;
  628.     for(const auto& mu : M){
  629.         vector<double> mu_values;
  630.         vector<double> args;
  631.         for(int i = 0; i < mu.size(); ++i){
  632.             mu_values.push_back(static_cast<double>(mu[i]));
  633.             args.push_back(static_cast<double>(x[i]));
  634.         }
  635.         f_values.push_back(mu_values);
  636.         vec_M.push_back(args);
  637.     }
  638.     int count = 0;
  639.     for(size_t i = 0; i < vec_M.size(); ++i){
  640.         coefs g = get_polynomial(vec_M[i], f_values[i]);
  641.         // cout << count++ << '\n';
  642.         variant<bool, polynomial<int>> check = type_check(g);
  643.         polynomial<int> h;
  644.         if(holds_alternative<polynomial<int>>(check)){
  645.             h = get<polynomial<int>>(check);
  646.             if(h == polynomial<int>(0)){
  647.                 // cout << h << '\n';
  648.                 continue;
  649.             }
  650.             if(h[h.degree()] > ans.prf[ans.prf.degree()]){
  651.                 continue;
  652.             }
  653.             // cout << ans.prf << '\n';
  654.             // cout << h << '\n';
  655.             if(h[h.degree()] < 0){
  656.                 h *= -1;
  657.             }
  658.             // cout << h << '\n';
  659.             pair<polynomial<double>, polynomial<double>> tmp = quotient_remainder(ans.prf, h);
  660.             variant<bool, polynomial<int>> second_check = type_check(tmp.first.data());
  661.             if(holds_alternative<bool>(second_check)){
  662.                 continue;
  663.             }
  664.             polynomial<int> res = get<polynomial<int>>(second_check);
  665.             if(h.degree() >= 1 && tmp.second == polynomial<double>(0)){
  666.                 ans.driven = false;
  667.                 ans.x_a = h;
  668.                 ans.quo = ContPrim(res).second;
  669.                 return ans;
  670.             }
  671.         }else{
  672.             continue;
  673.         }        
  674.     }
  675.     ans.driven = true;
  676.     ans.x_a = ans.prf;
  677.     ans.quo = polynomial<int>(1);
  678.     return ans;
  679. }
  680.  
  681. struct Kroneker kronekerIRR(polynomial<int> f){
  682.     Kroneker kr = kroneker(f);
  683.     if(kr.driven){
  684.         return kr;
  685.     }
  686.     polynomial<int> h = kr.x_a;
  687.     while(!kroneker(h).driven){
  688.         // cout << h << '\n';
  689.         h = kroneker(h).x_a;
  690.     }
  691.     kr.driven = false;
  692.     kr.x_a = h;
  693.     kr.quo = ContPrim(quotient_remainder(kr.prf, h).first).second;
  694.     // kr.quo = quotient_remainder(kr.prf, h).first;
  695.     return kr;
  696. }
  697.  
  698. using kronekerFactsValue = pair<int, vector<pair<polynomial<int>, int>>>;
  699.  
  700. int ListSearch(vector<polynomial<int>>& list, polynomial<int> target) {
  701.     auto it = find(list.begin(), list.end(), target);
  702.     if (it != list.end()) {
  703.         return it - list.begin();  // +1 because Maple uses 1-based indexing
  704.     } else {
  705.         return -1;
  706.     }
  707. }
  708.  
  709. int sum(vector<int>& vec){
  710.     int res = 0;
  711.     for(const auto& it : vec){
  712.         res += it;
  713.     }
  714.     return res;
  715. }
  716.  
  717. variant<polynomial<int>, kronekerFactsValue> kronekerFacts(polynomial<int> f){
  718.     int n = f.degree();
  719.     if(n <= 1){
  720.         return f;
  721.     }
  722.     int scal;
  723.     polynomial<int> prf;
  724.     pair<int, polynomial<int>> tmp_cont = ContPrim(f);
  725.     scal = tmp_cont.first;
  726.     prf = tmp_cont.second;
  727.     struct Kroneker kr = kronekerIRR(prf);
  728.     polynomial<int> g = kr.x_a;
  729.     polynomial<int> h = kr.quo;
  730.     vector<polynomial<int>> irr = {g};
  731.     vector<int> mlt = {1};
  732.     cout << g << '\n';
  733.     cout << h << '\n';
  734.     // return f;
  735.     while(h != polynomial<int>(1)){
  736.         kr = kronekerIRR(h);
  737.         g = kr.x_a;
  738.         h = kr.quo;
  739.         cout << g << '\n';
  740.         cout << h << '\n';
  741.         auto k = ListSearch(irr, g);
  742.         // cout << k << '\n';
  743.         if (k == -1) {
  744.             irr.push_back(g);
  745.             mlt.push_back(1);
  746.         } else {
  747.             mlt[k] += 1;
  748.         }
  749.     }
  750.     kronekerFactsValue ans;
  751.     for(size_t i = 0; i < irr.size(); ++i){
  752.         ans.second.push_back(make_pair(irr[i], mlt[i]));
  753.     }
  754.     ans.first = scal;
  755.     return ans;
  756. }
  757.  
  758. int main0()
  759. {  
  760.     std::cout << "Using Boost "    
  761.           << BOOST_VERSION / 100000     << "."  // major version
  762.           << BOOST_VERSION / 100 % 1000 << "."  // minor version
  763.           << BOOST_VERSION % 100                // patch level
  764.           << std::endl;
  765.     // vector<set<int>> U = {{1, 2}, {3, 4, 5, 7}, {8, 9}}; // Пример списка множеств U
  766.  
  767.     // set<vector<int>> result = CartesianLS(U);
  768.     // cout << "Cartesian product of U: ";
  769.     // for (const vector<int> &list : result)
  770.     // {
  771.     //     printVector(list);
  772.     //     cout << " ";
  773.     // }
  774.     // cout << endl;
  775.  
  776.     return 0;
  777. }
  778.  
  779. int main1()
  780. {
  781.     set<int> A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; // Пример множества A
  782.  
  783.     set<vector<int>> result = SetOfLists(A);
  784.     cout << "Set of lists B: ";
  785.     for (const vector<int> &list : result)
  786.     {
  787.         printVector(list);
  788.         cout << " ";
  789.     }
  790.     cout << endl;
  791.  
  792.     return 0;
  793. }
  794.  
  795. int main2()
  796. {
  797.     set<vector<int>> A = {{1}, {2}, {4}};                  // Пример множества A
  798.     set<vector<int>> B = {{1, 1}, {1, 2}, {2, 1}, {2, 2}}; // Пример множества B
  799.  
  800.     vector<vector<int>> result = CartesianSL(A, B);
  801.     cout << "Cartesian product of A and B: ";
  802.     for (const vector<int> &pair : result)
  803.     {
  804.         printVector(pair);
  805.         cout << " ";
  806.     }
  807.     cout << endl;
  808.  
  809.     return 0;
  810. }
  811.  
  812. int main3()
  813. {
  814.     set<int> B = {1, 2, 3}; // Пример множества A
  815.     set<int> A = {4, 5};    // Пример множества B
  816.  
  817.     set<pair<int, int>> result = CartesianS(A, B);
  818.     cout << "Cartesian product of A and B: ";
  819.     for (auto it = result.begin(); it != result.end(); ++it)
  820.     {
  821.         cout << "(" << it->first << ", " << it->second << ") ";
  822.     }
  823.     cout << endl;
  824.  
  825.     return 0;
  826. }
  827.  
  828. int main4()
  829. {
  830.     set<int> A;
  831.     int a = -12;
  832.     printSet(toPrimeNumbers(a));
  833.     return 0;
  834. }
  835.  
  836. int main(){
  837.     polynomial<int> f({1, 2, 2, 3, 3, 2, 2, 1});
  838.     polynomial<int> h({1, -1, 1});
  839.     polynomial<int> g({1, 1});
  840.     vector<polynomial<int>> tmp = {f, h, g, g, h};
  841.     kronekerFactsValue ans;
  842.     ans = get<kronekerFactsValue>(kronekerFacts(f));
  843.     cout << ans.first << '\n';
  844.     for(int i = 0; i < ans.second.size(); ++i){
  845.         cout << ans.second[i].first << " " << ans.second[i].second << '\n';
  846.     }
  847.     return 0;
  848. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!