Submit Info #12752

Problem Lang User Status Time Memory
Factorize cpp sansen RE 10000 ms 0.72 MiB

ケース詳細
Name Status Time Memory
big2_00 AC 556 ms 0.72 MiB
big2_01 AC 515 ms 0.67 MiB
big2_02 AC 554 ms 0.67 MiB
example_00 AC 0 ms 0.67 MiB
random_00 TLE 10000 ms 0.67 MiB
random_01 TLE 10000 ms 0.68 MiB
random_02 RE 4078 ms 0.68 MiB
small_00 AC 0 ms 0.71 MiB
small_01 AC 2 ms 0.68 MiB
small_02 AC 3 ms 0.68 MiB

#include <bits/stdc++.h> using namespace std; using int64 = long long; using int128 = __int128_t; constexpr int DEBUG = 0; int PowerMod(int128 base, int64 power, int64 mod) { base %= mod; int64 result = 1; while (power > 0) { if (power % 2 == 1) { result = (result * base) % mod; } base = (base * base) % mod; power /= 2; } return result; } bool IsPrimeMillarRabin(int64 x) { if (x == 1) return false; if (x == 2) return true; if (x % 2 == 0) return false; int s = 0; int64 d = x - 1; while (d % 2 == 0) { s++; d /= 2; } for (int a : {2, 3, 61}) { if (a >= x) continue; int128 y = PowerMod(a, d, x); if (y == 1 || y == x - 1) continue; for (int i = 0; i < s; i++) { y = (y * y) % x; if (y == x - 1) break; } if (y == x - 1) continue; return false; } return true; } vector<int64> FactorizePollardRho(int64 n) { static const vector<int> kPrimes = {2, 3, 5, 7, 11, 13, 17, 19}; vector<int64> ps; for (int prime : kPrimes) { while (n % prime == 0) { n /= prime; ps.push_back(prime); } } function<void(int64, vector<int64>&)> extract_fn = [&extract_fn](int64 n, vector<int64>&ps) { if (n == 1) return; if (IsPrimeMillarRabin(n)) { ps.push_back(n); return; } for (int c = 1; c <= 100; c++) { int128 x = 2; int128 y = 2; int64 d = 1; while (d == 1) { x = (x * x + c) % n; y = (y * y + c) % n; y = (y * y + c) % n; // d = __gcd(static_cast<int64>(abs(x - y)), n); d = __gcd(abs(static_cast<int64>(x - y)), n); } if (d == n) { continue; } extract_fn(d, ps); extract_fn(n / d, ps); return; } cerr << "FactorizePollardRho() failed!" << endl; exit(1); }; extract_fn(n, ps); sort(ps.begin(), ps.end()); return ps; // vector<pair<int64, int>> outputs; // for (int p : ps) { // if (outputs.empty()) { // outputs.push_back({p, 1}); // } else if (outputs.back().first == p) { // outputs.back().second++; // } else { // outputs.push_back({p, 1}); // } // } // return outputs; } int main() { int q_count; cin >> q_count; for (int i = 0; i < q_count; i++) { int64 x; cin >> x; auto ps = FactorizePollardRho(x); cout << ps.size(); for (int i = 0; i < ps.size(); i++) { cout << " "; cout << ps[i]; } cout << endl; } }