GCC Code Coverage Report


Directory: ./
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 100.0% 77 / 0 / 77
Functions: 100.0% 8 / 0 / 8
Branches: 64.9% 144 / 0 / 222

test/cpv_local/nt/lsieve_func.cpp
Line Branch Exec Source
1 // competitive-verifier: STANDALONE
2
3 #include "../../../src/math/qpow/basic/lib.hpp"
4 #include "../../../src/nt/gl/gcd/lib.hpp"
5 #include "../../../src/nt/lsieve/func/lib.hpp"
6 #include "../../../src/nt/lsieve/impl1/lib.hpp"
7 #include "../../../src/nt/lsieve/impl2/lib.hpp"
8 #include "../base.hpp"
9
10 using namespace tifa_libs;
11 struct lsieve_bf {
12 vecu prime, mpf, phi, tau;
13 veci mu;
14 vecuu sigma;
15
16 11 constexpr lsieve_bf& reset_lsieve_bf(u32 n) {
17
2/2
✓ Branch 0 taken 28092 times.
✓ Branch 1 taken 11 times.
28103 flt_ (u32, i, 2, n) {
18 28092 bool f = 1;
19
2/2
✓ Branch 0 taken 259021 times.
✓ Branch 1 taken 18 times.
259039 flt_ (u32, j, 2, i - 1) {
20
2/2
✓ Branch 0 taken 24260 times.
✓ Branch 1 taken 234761 times.
259021 if (i % j == 0) {
21 24260 f = 0;
22 24260 break;
23 }
24
2/2
✓ Branch 0 taken 3814 times.
✓ Branch 1 taken 230947 times.
234761 if (j > (i + j - 1) / j) break;
25 }
26
3/4
✓ Branch 0 taken 3832 times.
✓ Branch 1 taken 24260 times.
✓ Branch 3 taken 3832 times.
✗ Branch 4 not taken.
28092 if (f) prime.push_back(i);
27 }
28
4/6
✓ Branch 1 taken 11 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 9 times.
✓ Branch 5 taken 2 times.
✓ Branch 7 taken 9 times.
✗ Branch 8 not taken.
11 mpf = vecu(n), (n > 1) && (mpf[1] = 1);
29
2/2
✓ Branch 0 taken 28092 times.
✓ Branch 1 taken 11 times.
28103 flt_ (u32, i, 2, n) {
30
1/2
✓ Branch 5 taken 1296733 times.
✗ Branch 6 not taken.
1296733 for (auto j : prime) {
31
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1296733 times.
1296733 if (i < j) break;
32
2/2
✓ Branch 0 taken 28092 times.
✓ Branch 1 taken 1268641 times.
1296733 if (i % j == 0) {
33 28092 mpf[i] = j;
34 28092 break;
35 }
36 }
37 }
38
4/6
✓ Branch 1 taken 11 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 9 times.
✓ Branch 5 taken 2 times.
✓ Branch 7 taken 9 times.
✗ Branch 8 not taken.
11 phi = vecu(n), (n > 1) && (phi[1] = 1);
39
2/2
✓ Branch 0 taken 28092 times.
✓ Branch 1 taken 11 times.
28103 flt_ (u32, i, 2, n)
40
2/2
✓ Branch 2 taken 69990986 times.
✓ Branch 3 taken 28092 times.
70019078 flt_ (u32, j, 1, i + 1) phi[i] += (gcd(i, j) == 1);
41
4/6
✓ Branch 1 taken 11 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 9 times.
✓ Branch 5 taken 2 times.
✓ Branch 7 taken 9 times.
✗ Branch 8 not taken.
11 tau = vecu(n), (n > 1) && (tau[1] = 1);
42
2/2
✓ Branch 0 taken 28092 times.
✓ Branch 1 taken 11 times.
28103 flt_ (u32, i, 2, n)
43
2/2
✓ Branch 1 taken 69990986 times.
✓ Branch 2 taken 28092 times.
70019078 flt_ (u32, j, 1, i + 1) tau[i] += (i % j == 0);
44
4/6
✓ Branch 1 taken 11 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 9 times.
✓ Branch 5 taken 2 times.
✓ Branch 7 taken 9 times.
✗ Branch 8 not taken.
11 mu = veci(n), (n > 1) && (mu[1] = 1);
45
2/2
✓ Branch 0 taken 28092 times.
✓ Branch 1 taken 11 times.
28103 flt_ (u32, i, 2, n) {
46 28092 mu[i] = 1;
47
2/2
✓ Branch 5 taken 6108433 times.
✓ Branch 6 taken 27 times.
6108460 for (auto j : prime) {
48
2/2
✓ Branch 0 taken 17054 times.
✓ Branch 1 taken 6091379 times.
6108433 if (i < j) break;
49
2/2
✓ Branch 0 taken 49979 times.
✓ Branch 1 taken 6041400 times.
6091379 if (i % j == 0) {
50
2/2
✓ Branch 0 taken 11011 times.
✓ Branch 1 taken 38968 times.
49979 if ((i / j) % j == 0) {
51 11011 mu[i] = 0;
52 11011 break;
53 }
54 38968 mu[i] *= -1;
55 }
56 }
57 }
58
4/6
✓ Branch 1 taken 11 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 9 times.
✓ Branch 5 taken 2 times.
✓ Branch 7 taken 9 times.
✗ Branch 8 not taken.
11 sigma = vecuu(n), (n > 1) && (sigma[1] = 1);
59
2/2
✓ Branch 0 taken 28092 times.
✓ Branch 1 taken 11 times.
28103 flt_ (u32, i, 2, n)
60
2/2
✓ Branch 1 taken 69990986 times.
✓ Branch 2 taken 28092 times.
70019078 flt_ (u32, j, 1, i + 1) sigma[i] += (i % j == 0) * j;
61
62 11 return *this;
63 }
64 };
65
66 struct lsieve_func2 {
67 vecu phi, tau;
68 veci mu;
69 vecuu sigma;
70
71 11 constexpr lsieve_func2& reset_lsieve_func2(u32 n) {
72 11 auto ls = lsieve2(n);
73
1/2
✗ Branch 3 not taken.
✓ Branch 4 taken 4109 times.
4120 phi = ls.run<u32>([](u32 p, u32 i) -> u32 { retif_((i == 0), 1, u32(qpow((u64)p, i) - qpow((u64)p, i - 1))); });
74 4120 tau = ls.run<u32>([](u32, u32 i) -> u32 { return i + 1; });
75 22 mu = ls.run<i32>([](u32, u32 i) -> i32 {
76
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4109 times.
4109 if (i == 0) return 1;
77
2/2
✓ Branch 0 taken 3832 times.
✓ Branch 1 taken 277 times.
4109 else retif_((i == 1), -1, 0);
78 11 });
79
1/2
✗ Branch 3 not taken.
✓ Branch 4 taken 4109 times.
4120 sigma = ls.run<u64>([](u32 p, u32 i) -> u64 { retif_((i == 0), 1, (qpow((u64)p, i + 1) - 1) / (p - 1)); });
80 22 return *this;
81 11 }
82 };
83
84 11 void test(u32 n) {
85 11 lsieve_bf lsb;
86
4/8
✓ Branch 2 taken 11 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 11 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 11 times.
✗ Branch 10 not taken.
✓ Branch 12 taken 11 times.
✗ Branch 13 not taken.
11 timer_(lsb.reset_lsieve_bf(n));
87
88
3/6
✓ Branch 4 taken 11 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 11 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 11 times.
✗ Branch 11 not taken.
11 timer_(lsieve<ls_mpf, ls_mu, ls_phi, ls_sigma, ls_tau> lsf(n));
89
90
1/2
✓ Branch 4 taken 11 times.
✗ Branch 5 not taken.
11 check(lsf.primes, lsb.prime);
91
4/6
✓ Branch 1 taken 28111 times.
✗ Branch 2 not taken.
✓ Branch 9 taken 28111 times.
✗ Branch 10 not taken.
✓ Branch 12 taken 28111 times.
✓ Branch 13 taken 11 times.
28122 flt_ (u32, i, 0, n) check(lsf.mpf[i], lsb.mpf[i], check_param(i));
92
4/6
✓ Branch 1 taken 28111 times.
✗ Branch 2 not taken.
✓ Branch 9 taken 28111 times.
✗ Branch 10 not taken.
✓ Branch 12 taken 28111 times.
✓ Branch 13 taken 11 times.
28122 flt_ (u32, i, 0, n) check(lsf.phi[i], lsb.phi[i], check_param(i));
93
4/6
✓ Branch 1 taken 28111 times.
✗ Branch 2 not taken.
✓ Branch 9 taken 28111 times.
✗ Branch 10 not taken.
✓ Branch 12 taken 28111 times.
✓ Branch 13 taken 11 times.
28122 flt_ (u32, i, 0, n) check(lsf.tau[i], lsb.tau[i], check_param(i));
94
4/6
✓ Branch 1 taken 28111 times.
✗ Branch 2 not taken.
✓ Branch 9 taken 28111 times.
✗ Branch 10 not taken.
✓ Branch 12 taken 28111 times.
✓ Branch 13 taken 11 times.
28122 flt_ (u32, i, 0, n) check(lsf.mu[i], lsb.mu[i], check_param(i));
95
4/6
✓ Branch 1 taken 28111 times.
✗ Branch 2 not taken.
✓ Branch 9 taken 28111 times.
✗ Branch 10 not taken.
✓ Branch 12 taken 28111 times.
✓ Branch 13 taken 11 times.
28122 flt_ (u32, i, 0, n) check(lsf.sigma[i], lsb.sigma[i], check_param(i));
96
97 11 lsieve_func2 lsf2;
98
3/6
✓ Branch 4 taken 11 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 11 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 11 times.
✗ Branch 11 not taken.
11 timer_(lsf2.reset_lsieve_func2(n));
99
100
4/6
✓ Branch 1 taken 28111 times.
✗ Branch 2 not taken.
✓ Branch 9 taken 28111 times.
✗ Branch 10 not taken.
✓ Branch 12 taken 28111 times.
✓ Branch 13 taken 11 times.
28122 flt_ (u32, i, 0, n) check(lsf2.phi[i], lsb.phi[i], check_param(i));
101
4/6
✓ Branch 1 taken 28111 times.
✗ Branch 2 not taken.
✓ Branch 9 taken 28111 times.
✗ Branch 10 not taken.
✓ Branch 12 taken 28111 times.
✓ Branch 13 taken 11 times.
28122 flt_ (u32, i, 0, n) check(lsf2.tau[i], lsb.tau[i], check_param(i));
102
4/6
✓ Branch 1 taken 28111 times.
✗ Branch 2 not taken.
✓ Branch 9 taken 28111 times.
✗ Branch 10 not taken.
✓ Branch 12 taken 28111 times.
✓ Branch 13 taken 11 times.
28122 flt_ (u32, i, 0, n) check(lsf2.mu[i], lsb.mu[i], check_param(i));
103
4/6
✓ Branch 1 taken 28111 times.
✗ Branch 2 not taken.
✓ Branch 9 taken 28111 times.
✗ Branch 10 not taken.
✓ Branch 12 taken 28111 times.
✓ Branch 13 taken 11 times.
28122 flt_ (u32, i, 0, n) check(lsf2.sigma[i], lsb.sigma[i], check_param(i));
104 11 }
105
106 1 int main() {
107
3/6
✓ Branch 4 taken 1 time.
✗ Branch 5 not taken.
✓ Branch 7 taken 1 time.
✗ Branch 8 not taken.
✓ Branch 10 taken 1 time.
✗ Branch 11 not taken.
1 timer_(test(0));
108
3/6
✓ Branch 4 taken 1 time.
✗ Branch 5 not taken.
✓ Branch 7 taken 1 time.
✗ Branch 8 not taken.
✓ Branch 10 taken 1 time.
✗ Branch 11 not taken.
1 timer_(test(1));
109
3/6
✓ Branch 4 taken 1 time.
✗ Branch 5 not taken.
✓ Branch 7 taken 1 time.
✗ Branch 8 not taken.
✓ Branch 10 taken 1 time.
✗ Branch 11 not taken.
1 timer_(test(10));
110
3/6
✓ Branch 4 taken 1 time.
✗ Branch 5 not taken.
✓ Branch 7 taken 1 time.
✗ Branch 8 not taken.
✓ Branch 10 taken 1 time.
✗ Branch 11 not taken.
1 timer_(test(100));
111
3/6
✓ Branch 4 taken 1 time.
✗ Branch 5 not taken.
✓ Branch 7 taken 1 time.
✗ Branch 8 not taken.
✓ Branch 10 taken 1 time.
✗ Branch 11 not taken.
1 timer_(test(1000));
112
3/6
✓ Branch 4 taken 1 time.
✗ Branch 5 not taken.
✓ Branch 7 taken 1 time.
✗ Branch 8 not taken.
✓ Branch 10 taken 1 time.
✗ Branch 11 not taken.
1 timer_(test(2000));
113
3/6
✓ Branch 4 taken 1 time.
✗ Branch 5 not taken.
✓ Branch 7 taken 1 time.
✗ Branch 8 not taken.
✓ Branch 10 taken 1 time.
✗ Branch 11 not taken.
1 timer_(test(3000));
114
3/6
✓ Branch 4 taken 1 time.
✗ Branch 5 not taken.
✓ Branch 7 taken 1 time.
✗ Branch 8 not taken.
✓ Branch 10 taken 1 time.
✗ Branch 11 not taken.
1 timer_(test(4000));
115
3/6
✓ Branch 4 taken 1 time.
✗ Branch 5 not taken.
✓ Branch 7 taken 1 time.
✗ Branch 8 not taken.
✓ Branch 10 taken 1 time.
✗ Branch 11 not taken.
1 timer_(test(5000));
116
3/6
✓ Branch 4 taken 1 time.
✗ Branch 5 not taken.
✓ Branch 7 taken 1 time.
✗ Branch 8 not taken.
✓ Branch 10 taken 1 time.
✗ Branch 11 not taken.
1 timer_(test(6000));
117
3/6
✓ Branch 4 taken 1 time.
✗ Branch 5 not taken.
✓ Branch 7 taken 1 time.
✗ Branch 8 not taken.
✓ Branch 10 taken 1 time.
✗ Branch 11 not taken.
1 timer_(test(7000));
118 1 }
119