Advertisement
gmusya

Untitled

Aug 21st, 2022
56
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.70 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <set>
  4.  
  5. using namespace std;
  6.  
  7. using int128 = __int128_t;
  8. using uint128 = __uint128_t;
  9. using uint64 = unsigned long long;
  10.  
  11. uint64 p = 3;
  12.  
  13. uint128 bin_up(uint128 value, uint128 power, uint128 modulo) {
  14. if (!power) {
  15. return 1;
  16. } else if (power & 1) {
  17. return bin_up(value, power - 1, modulo) * value % modulo;
  18. } else {
  19. uint128 tmp = bin_up(value, power >> 1, modulo);
  20. return tmp * tmp % modulo;
  21. }
  22. }
  23.  
  24. uint128 inv(uint128 value, uint128 modulo) {
  25. return bin_up(value, modulo - 2, modulo);
  26. }
  27.  
  28. struct Polynomial {
  29. vector <uint128> values;
  30.  
  31. Polynomial() = default;
  32.  
  33. explicit Polynomial(const vector <uint128>& vec) {
  34. values = vec;
  35. }
  36.  
  37. friend ostream& operator<<(ostream& out, const Polynomial& polynomial) {
  38. for (auto& now: polynomial.values) {
  39. out << uint64(now) << ' ';
  40. }
  41. return out;
  42. }
  43.  
  44. Polynomial operator*(const Polynomial& other) const {
  45. Polynomial result;
  46. result.values.resize(values.size() + other.values.size() - 1);
  47. for (size_t i = 0; i < values.size(); ++i) {
  48. for (size_t j = 0; j < other.values.size(); ++j) {
  49. result.values[i + j] += values[i] * other.values[j];
  50. result.values[i + j] %= p;
  51. }
  52. }
  53. while (result.values.size() > 1 && result.values.back() == 0) {
  54. result.values.pop_back();
  55. }
  56. return result;
  57. }
  58.  
  59. Polynomial operator*(const uint128 value) const {
  60. Polynomial result = *this;
  61. for (auto& now: result.values) {
  62. now = now * value % p;
  63. }
  64. return result;
  65. }
  66.  
  67. Polynomial operator-(const Polynomial& other) const {
  68. Polynomial result = *this;
  69. if (result.values.size() < other.values.size()) {
  70. result.values.resize(other.values.size());
  71. }
  72. for (uint128 i = 0; i < other.values.size(); ++i) {
  73. if (result.values[i] < other.values[i]) {
  74. result.values[i] += p;
  75. }
  76. result.values[i] -= other.values[i];
  77. }
  78. while (result.values.size() > 1 && result.values.back() == 0) {
  79. result.values.pop_back();
  80. }
  81. return result;
  82. }
  83.  
  84. bool operator!=(const Polynomial& other) const {
  85. if (this->values.size() != other.values.size()) {
  86. return true;
  87. }
  88. for (uint128 i = 0; i < other.values.size(); ++i) {
  89. if (values[i] != other.values[i]) {
  90. return true;
  91. }
  92. }
  93. return false;
  94. }
  95.  
  96. Polynomial operator%(const Polynomial& other) const {
  97. return *this - (*this / other) * other;
  98. }
  99.  
  100. Polynomial operator+(const Polynomial& other) const {
  101. vector <uint128> v(max(other.values.size(), values.size()));
  102. for (uint128 i = 0; i < other.values.size(); ++i) {
  103. v[i] += other.values[i];
  104. }
  105. for (uint128 i = 0; i < values.size(); ++i) {
  106. v[i] += values[i];
  107. if (v[i] >= p) {
  108. v[i] %= p;
  109. }
  110. }
  111. while (v.size() > 1 && v.back() == 0) {
  112. v.pop_back();
  113. }
  114. return Polynomial(v);
  115. }
  116.  
  117. Polynomial operator/(const Polynomial& other) const {
  118. if (values.size() < other.values.size()) {
  119. return Polynomial({0});
  120. }
  121. Polynomial rem = *this;
  122. Polynomial result({0});
  123. while (rem.values.size() >= other.values.size()) {
  124. if (rem.values.size() == 1 && rem.values.back() == 0) {
  125. break;
  126. }
  127. vector <uint128> vec(rem.values.size() - other.values.size() + 1);
  128. vec.back() = inv(other.values.back(), p) * rem.values.back() % p;
  129. Polynomial multiplier(vec);
  130. // cout << endl << "mult = " << multiplier << endl;
  131. rem = rem - multiplier * other;
  132. result = result + multiplier;
  133. }
  134. return result;
  135. }
  136.  
  137. void Normalize() {
  138. uint128 multiplier = inv(values.back(), p);
  139. for (auto& now: values) {
  140. now = now * multiplier % p;
  141. }
  142. }
  143. };
  144.  
  145.  
  146. int main() {
  147. int x = -1, y, z;
  148. for (int a = 0; a < p && x == -1; ++a) {
  149. for (int b = 0; b < p && x == -1; ++b) {
  150. for (int c = 0; c < p && x == -1; ++c) {
  151. bool good = true;
  152. for (int d = 0; d < p; ++d) {
  153. if ((d * d * d + c * d * d + b * d + a) % p == 0) {
  154. good = false;
  155. }
  156. }
  157. if (good) {
  158. x = a;
  159. y = b;
  160. z = c;
  161. }
  162. }
  163. }
  164. }
  165. Polynomial f;
  166. f.values.push_back(x);
  167. f.values.push_back(y);
  168. f.values.push_back(z);
  169. f.values.push_back(1);
  170. for (int a = 0; a < p; ++a) {
  171. for (int b = 0; b < p; ++b) {
  172. for (int c = 0; c < p; ++c) {
  173. if (a == 0 && b == 0 && c == 0) {
  174. continue;
  175. }
  176. Polynomial g;
  177. g.values.push_back(a);
  178. g.values.push_back(b);
  179. g.values.push_back(c);
  180. Polynomial cur;
  181. cur.values.push_back(1);
  182. cur.values.push_back(0);
  183. cur.values.push_back(0);
  184. set<vector < uint128>>
  185. s;
  186. for (int pow = 0; pow + 1 < p * p * p; ++pow) {
  187. cur = cur * g % f;
  188. s.insert(cur.values);
  189. }
  190. if (s.size() == p * p * p - 1) {
  191. cout << a << ' ' << b << ' ' << c << endl;
  192. return 0;
  193. }
  194. }
  195. }
  196. }
  197. return 0;
  198. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement