library/test/yosupo/factorize.test.cpp

• View this file on GitHub
• Last update: 2024-03-15 16:55:35+06:00
• Problem: https://judge.yosupo.jp/problem/factorize

Depends on

• library/math/fastFactorize.hpp

Code

#include <bits/stdc++.h>
using namespace std;
#define PROBLEM "https://judge.yosupo.jp/problem/factorize"
#include "../../math/fastFactorize.hpp"

int main() {
    ios::sync_with_stdio(0);
    int q; cin>>q;
    while(q--) {
        ull a; cin>>a;
        vector<ull> f;
        factor(a, f);
        sort(f.begin(), f.end());
        cout<<f.size()<<' ';
        for(auto x: f) 
            cout<<x<<' ';
        cout<<'\n';
    }
    return 0;
}

#line 1 "library/test/yosupo/factorize.test.cpp"
#include <bits/stdc++.h>
using namespace std;
#define PROBLEM "https://judge.yosupo.jp/problem/factorize"
#line 1 "library/math/fastFactorize.hpp"
typedef int64_t ll;
typedef uint64_t ull;

ull mul(ull a, ull b, ull M) {
    ll r = a * b - M * ull(1.L / M * a * b);
    return r + M * ((r < 0) - (r >= (ll) M));
}
ull mow(ull x, ull e, ull M) {
    ull r = 1;
    for (; e; x = mul(x, x, M), e >>= 1)
        if (e & 1) r = mul(r, x, M);
    return r;
}

bool isPrime(ull n) {
    if (n < 2 or n % 6 % 4 != 1) return (n | 1) == 3;
    static const ull A[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41};
    ull s = __builtin_ctzll(n - 1), d = n >> s;
    for (const ull& a: A) {
        ull p = mow(a % n, d, n), i = s;
        while (p != 1 and p != n - 1 and a % n != 0 and i--)
            p = mul(p, p, n);
        if (p != n - 1 and i != s) return false;
    }
    return true;
}

ull pollard(ull n) {
    static mt19937_64 mt((unsigned)chrono::system_clock::now().time_since_epoch().count());
    static ull c = 1;
    auto f = [&](ull x) { return mul(x, x, n) + c; };
    ull x = 0, y = 0, t = 40, p = 2, q, i = 2;
    while (t++ % 30 or gcd(p, n) == 1) {
        if (x == y) c = mt() % (n - 1) + 1, y = f(x = ++i);
        if (q = mul(p, (x > y ? x - y : y - x), n)) p = q;
        x = f(x); y = f(f(y));
    }
    return gcd(p, n);
}

void factor(ull n, vector<ull>& f) {
    if (n == 1) return;
    if (isPrime(n)) {
        f.push_back(n);
        return;
    }
    ull x = pollard(n);
    factor(x, f);
    factor(n / x, f);
    return;
}
#line 5 "library/test/yosupo/factorize.test.cpp"

int main() {
    ios::sync_with_stdio(0);
    int q; cin>>q;
    while(q--) {
        ull a; cin>>a;
        vector<ull> f;
        factor(a, f);
        sort(f.begin(), f.end());
        cout<<f.size()<<' ';
        for(auto x: f) 
            cout<<x<<' ';
        cout<<'\n';
    }
    return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	4295098369_00	AC	9 ms	4 MB
g++	999381247093216751_00	AC	94 ms	4 MB
g++	big2_00	AC	90 ms	4 MB
g++	big2_01	AC	90 ms	4 MB
g++	big2_02	AC	99 ms	4 MB
g++	big2_worse_00	AC	97 ms	4 MB
g++	big_semiprime_gen_00	AC	94 ms	4 MB
g++	big_semiprime_gen_01	AC	82 ms	4 MB
g++	big_semiprime_random_00	AC	76 ms	4 MB
g++	big_semiprime_random_01	AC	71 ms	4 MB
g++	carmichael_00	AC	12 ms	4 MB
g++	example_00	AC	5 ms	4 MB
g++	fixed_RNG_buster_00	AC	5 ms	4 MB
g++	hack00_00	AC	5 ms	4 MB
g++	max_00	AC	12 ms	4 MB
g++	pow2_00	AC	13 ms	4 MB
g++	pow2_01	AC	13 ms	4 MB
g++	pow2_02	AC	18 ms	4 MB
g++	prime_test_special_00	AC	7 ms	4 MB
g++	prime_test_special_01	AC	8 ms	4 MB
g++	prime_test_special_02	AC	11 ms	4 MB
g++	prime_test_special_03	AC	7 ms	4 MB
g++	prime_test_special_bug_00	AC	6 ms	4 MB
g++	prime_test_special_bug_01	AC	7 ms	4 MB
g++	prime_test_special_bug_02	AC	6 ms	4 MB
g++	random_00	AC	7 ms	4 MB
g++	random_01	AC	7 ms	4 MB
g++	random_02	AC	9 ms	4 MB
g++	small_00	AC	6 ms	4 MB
g++	small_01	AC	6 ms	4 MB
g++	small_02	AC	6 ms	4 MB

Back to top page