Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <set>
- using namespace std;
- using int128 = __int128_t;
- using uint128 = __uint128_t;
- using uint64 = unsigned long long;
- uint64 p = 3;
- uint128 bin_up(uint128 value, uint128 power, uint128 modulo) {
- if (!power) {
- return 1;
- } else if (power & 1) {
- return bin_up(value, power - 1, modulo) * value % modulo;
- } else {
- uint128 tmp = bin_up(value, power >> 1, modulo);
- return tmp * tmp % modulo;
- }
- }
- uint128 inv(uint128 value, uint128 modulo) {
- return bin_up(value, modulo - 2, modulo);
- }
- struct Polynomial {
- vector <uint128> values;
- Polynomial() = default;
- explicit Polynomial(const vector <uint128>& vec) {
- values = vec;
- }
- friend ostream& operator<<(ostream& out, const Polynomial& polynomial) {
- for (auto& now: polynomial.values) {
- out << uint64(now) << ' ';
- }
- return out;
- }
- Polynomial operator*(const Polynomial& other) const {
- Polynomial result;
- result.values.resize(values.size() + other.values.size() - 1);
- for (size_t i = 0; i < values.size(); ++i) {
- for (size_t j = 0; j < other.values.size(); ++j) {
- result.values[i + j] += values[i] * other.values[j];
- result.values[i + j] %= p;
- }
- }
- while (result.values.size() > 1 && result.values.back() == 0) {
- result.values.pop_back();
- }
- return result;
- }
- Polynomial operator*(const uint128 value) const {
- Polynomial result = *this;
- for (auto& now: result.values) {
- now = now * value % p;
- }
- return result;
- }
- Polynomial operator-(const Polynomial& other) const {
- Polynomial result = *this;
- if (result.values.size() < other.values.size()) {
- result.values.resize(other.values.size());
- }
- for (uint128 i = 0; i < other.values.size(); ++i) {
- if (result.values[i] < other.values[i]) {
- result.values[i] += p;
- }
- result.values[i] -= other.values[i];
- }
- while (result.values.size() > 1 && result.values.back() == 0) {
- result.values.pop_back();
- }
- return result;
- }
- bool operator!=(const Polynomial& other) const {
- if (this->values.size() != other.values.size()) {
- return true;
- }
- for (uint128 i = 0; i < other.values.size(); ++i) {
- if (values[i] != other.values[i]) {
- return true;
- }
- }
- return false;
- }
- Polynomial operator%(const Polynomial& other) const {
- return *this - (*this / other) * other;
- }
- Polynomial operator+(const Polynomial& other) const {
- vector <uint128> v(max(other.values.size(), values.size()));
- for (uint128 i = 0; i < other.values.size(); ++i) {
- v[i] += other.values[i];
- }
- for (uint128 i = 0; i < values.size(); ++i) {
- v[i] += values[i];
- if (v[i] >= p) {
- v[i] %= p;
- }
- }
- while (v.size() > 1 && v.back() == 0) {
- v.pop_back();
- }
- return Polynomial(v);
- }
- Polynomial operator/(const Polynomial& other) const {
- if (values.size() < other.values.size()) {
- return Polynomial({0});
- }
- Polynomial rem = *this;
- Polynomial result({0});
- while (rem.values.size() >= other.values.size()) {
- if (rem.values.size() == 1 && rem.values.back() == 0) {
- break;
- }
- vector <uint128> vec(rem.values.size() - other.values.size() + 1);
- vec.back() = inv(other.values.back(), p) * rem.values.back() % p;
- Polynomial multiplier(vec);
- // cout << endl << "mult = " << multiplier << endl;
- rem = rem - multiplier * other;
- result = result + multiplier;
- }
- return result;
- }
- void Normalize() {
- uint128 multiplier = inv(values.back(), p);
- for (auto& now: values) {
- now = now * multiplier % p;
- }
- }
- };
- int main() {
- int x = -1, y, z;
- for (int a = 0; a < p && x == -1; ++a) {
- for (int b = 0; b < p && x == -1; ++b) {
- for (int c = 0; c < p && x == -1; ++c) {
- bool good = true;
- for (int d = 0; d < p; ++d) {
- if ((d * d * d + c * d * d + b * d + a) % p == 0) {
- good = false;
- }
- }
- if (good) {
- x = a;
- y = b;
- z = c;
- }
- }
- }
- }
- Polynomial f;
- f.values.push_back(x);
- f.values.push_back(y);
- f.values.push_back(z);
- f.values.push_back(1);
- for (int a = 0; a < p; ++a) {
- for (int b = 0; b < p; ++b) {
- for (int c = 0; c < p; ++c) {
- if (a == 0 && b == 0 && c == 0) {
- continue;
- }
- Polynomial g;
- g.values.push_back(a);
- g.values.push_back(b);
- g.values.push_back(c);
- Polynomial cur;
- cur.values.push_back(1);
- cur.values.push_back(0);
- cur.values.push_back(0);
- set<vector < uint128>>
- s;
- for (int pow = 0; pow + 1 < p * p * p; ++pow) {
- cur = cur * g % f;
- s.insert(cur.values);
- }
- if (s.size() == p * p * p - 1) {
- cout << a << ' ' << b << ' ' << c << endl;
- return 0;
- }
- }
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement