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 |