Problems Submissions
Register Login 質問(Gitter) GitHub

Submit Info #3647

Problem Lang User Status Time Memory
Factorize cpp (anonymous) WA 592 ms 0.64 MiB

ケース詳細
Name Status Time Memory
big2_00 AC 572 ms 0.62 MiB
big2_01 AC 592 ms 0.64 MiB
big2_02 AC 540 ms 0.59 MiB
example_00 WA 6 ms 0.64 MiB
random_00 WA 18 ms 0.55 MiB
random_01 WA 23 ms 0.55 MiB
random_02 WA 26 ms 0.63 MiB
small_00 WA 5 ms 0.59 MiB
small_01 WA 8 ms 0.54 MiB
small_02 WA 6 ms 0.62 MiB

#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; typedef long long ll; typedef pair<int,int> P; typedef pair<int,P> P1; typedef pair<P,P> P2; #define pu push #define pb push_back #define mp make_pair #define eps 1e-7 #define INF 1000000000 #define fi first #define sc second #define rep(i,x) for(int i=0;i<x;i++) #define repn(i,x) for(int i=1;i<=x;i++) #define SORT(x) sort(x.begin(),x.end()) #define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end()) #define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) #define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) #define lint long long ll gcd(ll a,ll b){ if(a < b) swap(a,b); if(b == 0) return a; else return gcd(b,a%b); } namespace miller_rabin{ lint mul(lint x, lint y, lint mod){ return (__int128) x * y % mod; } lint ipow(lint x, lint y, lint p){ lint ret = 1, piv = x % p; while(y){ if(y&1) ret = mul(ret, piv, p); piv = mul(piv, piv, p); y >>= 1; } return ret; } bool miller_rabin(lint x, lint a){ if(x % a == 0) return 0; lint d = x - 1; while(1){ lint tmp = ipow(a, d, x); if(d&1) return (tmp != 1 && tmp != x-1); else if(tmp == x-1) return 0; d >>= 1; } } bool isprime(lint x){ for(auto &i : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}){ if(x == i) return 1; if(x > 40 && miller_rabin(x, i)) return 0; } if(x <= 40) return 0; return 1; } }; namespace pollard_rho{ lint f(lint x, lint n, lint c){ return (c + miller_rabin::mul(x, x, n)) % n; } void rec(lint n, vector<lint> &v){ if(n == 1) return; if(n % 2 == 0){ v.push_back(2); rec(n/2, v); return; } if(miller_rabin::isprime(n)){ v.push_back(n); return; } lint a, b, c; while(1){ a = rand() % (n-2) + 2; b = a; c = rand() % 20 + 1; do{ a = f(a, n, c); b = f(f(b, n, c), n, c); }while(gcd(abs(a-b), n) == 1); if(a != b) break; } lint x = gcd(abs(a-b), n); rec(x, v); rec(n/x, v); } vector<lint> factorize(lint n){ vector<lint> ret; rec(n, ret); sort(ret.begin(), ret.end()); ERASE(ret); return ret; } }; int main(){ int q; cin >> q; while(q--){ ll a; cin >> a; auto ret = pollard_rho::factorize(a); cout << ret.size() << '\n'; rep(i,ret.size()) cout << ret[i] << '\n'; } }