GCC Code Coverage Report

Directory: ./
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 100.0% 59 / 0 / 59
Functions: 100.0% 7 / 0 / 7
Branches: 98.0% 49 / 0 / 50
src/nt/pfactors/lib.hpp
Line Branch Exec Source
1 #pragma once
2
3 #include "../../edh/discretization/lib.hpp"
4 #include "../../math/mul_mod/lib.hpp"
5 #include "../../util/rand/lib.hpp"
6 #include "../gl/gcd/lib.hpp"
7 #include "../is_prime/lib.hpp"
8
9 namespace tifa_libs {
10 namespace pfactors_impl_ {
11 static rand_gen<u64> e;
12 19055 static auto __ = [] { e.seed(); return 0; }();
13 98558 CEXP u64 rho(u64 n) NE {
14 98558 e.range(1, n - 1);
15 3080513223 auto f = [n, r = e()](u64 x) NE { return (mul_mod_u(x, x, n) + r) % n; };
16 98558 u64 g = 1, x = 0, y = e(), yy = 0;
17 98558 cu32 LIM = 128;
18
2/2
✓ Branch 0 taken 215680 times.
✓ Branch 1 taken 98558 times.
 314238 for (u64 r = 1, q = 1; g == 1; r *= 2) {
19 215680 x = y;
20
2/2
✓ Branch 1 taken 1869494050 times.
✓ Branch 2 taken 215680 times.
 1869709730 flt_ (u64, i, 0, r) y = f(y);
21
4/4
✓ Branch 0 taken 9770775 times.
✓ Branch 1 taken 98558 times.
✓ Branch 2 taken 9653653 times.
✓ Branch 3 taken 117122 times.
 9869333 for (u64 k = 0; g == 1 && k < r; k += LIM) {
22 9653653 yy = y;
23
4/4
✓ Branch 2 taken 1211087758 times.
✓ Branch 3 taken 9453353 times.
✓ Branch 4 taken 1210887458 times.
✓ Branch 5 taken 200300 times.
 1220541111 for (u64 i = 0; i < LIM && i < r - k; ++i) q = mul_mod_u(q, (n - (y = f(y)) + x) % n, n);
24 9653653 g = gcd(q, n);
25 }
26 }
27
2/2
✓ Branch 0 taken 25453 times.
✓ Branch 1 taken 73105 times.
 98558 if (g == n) do {
28 33157 g = gcd((x + (n - (yy = f(yy)))) % n, n);
29
2/2
✓ Branch 0 taken 7704 times.
✓ Branch 1 taken 25453 times.
 33157 } while (g == 1);
30
2/2
✓ Branch 0 taken 16139 times.
✓ Branch 1 taken 82419 times.
 98558 retif_((g == n), rho(n), g);
31 }
32 188127 CEXP void run(u64 n, vecuu& p) NE {
33
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 188127 times.
 188127 if (n < 2) return;
34
2/2
✓ Branch 1 taken 105708 times.
✓ Branch 2 taken 82419 times.
 188127 if (is_prime(n)) return p.push_back(n);
35 82419 cu64 g = rho(n);
36 82419 run(n / g, p), run(g, p);
37 }
38 } // namespace pfactors_impl_
39
40 template <bool unique = true>
41 299582 CEXP vecuu pfactors(u64 n) NE {
42 299582 vecuu p;
43
4/4
std::vector<unsigned long, std::allocator<unsigned long> > tifa_libs::pfactors<false>(unsigned long):
✓ Branch 1 taken 2822 times.
✓ Branch 2 taken 4816 times.
std::vector<unsigned long, std::allocator<unsigned long> > tifa_libs::pfactors<true>(unsigned long):
✓ Branch 1 taken 285964 times.
✓ Branch 2 taken 5980 times.
 299582 if (cu32 _ = (u32)std::countr_zero(n) & 63; _) {
44 288786 n >>= _;
45 285964 if CEXP (unique) p.push_back(2);
46 2822 else p.assign(_, 2);
47 }
48
4/4
std::vector<unsigned long, std::allocator<unsigned long> > tifa_libs::pfactors<false>(unsigned long):
✓ Branch 0 taken 1457 times.
✓ Branch 1 taken 6181 times.
std::vector<unsigned long, std::allocator<unsigned long> > tifa_libs::pfactors<true>(unsigned long):
✓ Branch 0 taken 274836 times.
✓ Branch 1 taken 17108 times.
 299582 if (n < 1000'000)
49
4/4
std::vector<unsigned long, std::allocator<unsigned long> > tifa_libs::pfactors<false>(unsigned long):
✓ Branch 0 taken 2515982 times.
✓ Branch 1 taken 1457 times.
std::vector<unsigned long, std::allocator<unsigned long> > tifa_libs::pfactors<true>(unsigned long):
✓ Branch 0 taken 24555061 times.
✓ Branch 1 taken 274836 times.
 27347336 for (u32 i = 3; i <= n; ++i) {
50
4/4
std::vector<unsigned long, std::allocator<unsigned long> > tifa_libs::pfactors<false>(unsigned long):
✓ Branch 0 taken 2514441 times.
✓ Branch 1 taken 1541 times.
std::vector<unsigned long, std::allocator<unsigned long> > tifa_libs::pfactors<true>(unsigned long):
✓ Branch 0 taken 24474464 times.
✓ Branch 1 taken 80597 times.
 27071043 if (n % i) continue;
51 80597 if CEXP (unique) p.push_back(i);
52 do {
53 205940 if CEXP (n /= i; !unique) p.push_back(i);
54
4/4
std::vector<unsigned long, std::allocator<unsigned long> > tifa_libs::pfactors<false>(unsigned long):
✓ Branch 0 taken 578 times.
✓ Branch 1 taken 1541 times.
std::vector<unsigned long, std::allocator<unsigned long> > tifa_libs::pfactors<true>(unsigned long):
✓ Branch 0 taken 123224 times.
✓ Branch 1 taken 80597 times.
 205940 } while (!(n % i));
55 }
56
4/4
std::vector<unsigned long, std::allocator<unsigned long> > tifa_libs::pfactors<false>(unsigned long):
✓ Branch 0 taken 1457 times.
✓ Branch 1 taken 6181 times.
std::vector<unsigned long, std::allocator<unsigned long> > tifa_libs::pfactors<true>(unsigned long):
✓ Branch 0 taken 274836 times.
✓ Branch 1 taken 17108 times.
 299582 if (n < 2) return p;
57 23289 pfactors_impl_::run(n, p);
58 17108 if CEXP (unique) return uniq(p);
59 6181 tifa_libs::sort(p);
60 6181 return p;
61 291944 }
62 4979 CEXP vecp<u64, u32> pf_exp(u64 n) NE {
63 4979 auto p = pfactors<false>(n);
64 4979 vecp<u64, u32> ans;
65
2/2
✓ Branch 5 taken 37544 times.
✓ Branch 6 taken 4979 times.
 42523 for (u64 lst = 0; cu64 i : p)
66
2/2
✓ Branch 0 taken 16535 times.
✓ Branch 1 taken 21009 times.
 37544 if (i != lst) ans.emplace_back(lst = i, 1);
67 21009 else ++ans.back().second;
68 4979 return ans;
69 4979 }
70
71 } // namespace tifa_libs
72