GCC Code Coverage Report

Directory: ./
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 100.0% 54 / 0 / 54
Functions: 100.0% 9 / 0 / 9
Branches: 88.5% 23 / 0 / 26
src/comb/seq/ipowi/lib.hpp
Line Branch Exec Source
1 #pragma once
2
3 #include "../../../math/iroot/sqrt/lib.hpp"
4 #include "../../../math/qpow/mod/lib.hpp"
5 #include "../../../nt/lsieve/impl1/lib.hpp"
6 #include "../../../nt/mod/barrett/lib.hpp"
7
8 namespace tifa_libs {
9 namespace gen_ipowi_impl_ {
10 struct ls_ipowi {
11 static inline u64 mod;
12 vecuu ipowi;
13
14 protected:
15 cu32 B;
16 vvecuu fp, fpb;
17 u32 pre_j{0}, gap{0};
18 u64 now_r{1};
19 arr<u64, 355> p{1}; // maximal prime gaps: g_n=354 => p_n=4,302,407,359
20
21 56 CEXPE ls_ipowi(u32 n) NE : ipowi(n), B{isqrt(n)}, fp(B + 1, vecuu(B + 1)), fpb(B + 1, vecuu(B + 1)) {
22
1/2
✓ Branch 0 taken 8 times.
✗ Branch 1 not taken.
 8 if (n) ipowi[0] = 1;
23
1/2
✓ Branch 0 taken 8 times.
✗ Branch 1 not taken.
 8 if (n > 1) ipowi[1] = 1;
24 8 }
25 314664 void prime(u32 p) NE {
26
2/2
✓ Branch 2 taken 716 times.
✓ Branch 3 taken 313948 times.
 314664 if (ipowi[p] = qpow_mod(p, p, mod); p <= B) {
27 716 fp[p][0] = 1;
28 716 barrett<0> brt(mod, ipowi[p]);
29
2/2
✓ Branch 0 taken 673364 times.
✓ Branch 1 taken 716 times.
 674080 flt_ (u32, j, 1, B + 1)
30 673364 fp[p][j] = brt.reduce(fp[p][j - 1]);
31 716 fpb[p][0] = 1;
32 716 brt.reset(mod, fp[p].back());
33
2/2
✓ Branch 0 taken 673364 times.
✓ Branch 1 taken 716 times.
 674080 flt_ (u32, j, 1, B + 1)
34 673364 fpb[p][j] = brt.reduce(fpb[p][j - 1]);
35 }
36 314664 }
37 3689320 void coprime(u32 i, u32 j) NE {
38
2/2
✓ Branch 0 taken 2001976 times.
✓ Branch 1 taken 1687344 times.
 3689320 if (j <= pre_j) now_r = 1, pre_j = gap = 0;
39 3689320 const barrett<0> brt(mod, ipowi[i]);
40
2/2
✓ Branch 0 taken 2117456 times.
✓ Branch 1 taken 1571864 times.
 3689320 if (cu32 new_gap = j - pre_j; new_gap > gap) {
41
2/2
✓ Branch 3 taken 4251808 times.
✓ Branch 4 taken 2117456 times.
 6369264 flt_ (u32, x, gap + 1, new_gap + 1) p[x] = brt.reduce(p[x - 1]);
42 2117456 gap = new_gap;
43 }
44 3689320 now_r = mul_mod_u(now_r, p[j - pre_j], mod);
45 3689320 ipowi[i * j] = mul_mod_u(mul_mod_u(fp[j][i % B], fpb[j][i / B], mod), now_r, mod);
46 3689320 pre_j = j;
47 3689320 }
48 1321632 void not_coprime(u32 i, u32 j) NE { coprime(i, j); }
49 };
50 } // namespace gen_ipowi_impl_
51
52 // i^i from i=0..n-1
53 8 CEXP vecuu gen_ipowi(u32 n, u64 mod) NE {
54
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 8 times.
 8 retif_((n < 2) [[unlikely]], vecuu(n, 1));
55 8 gen_ipowi_impl_::ls_ipowi::mod = mod;
56 8 return lsieve<gen_ipowi_impl_::ls_ipowi>(n).ipowi;
57 }
58 // i^i from i=0..n-1
59 template <class mint>
60 8 CEXP vec<mint> gen_ipowi(u32 n) NE {
61 8 vec<mint> ans(n);
62 8 auto _ = gen_ipowi(n, mint::mod());
63
8/8
std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<70l> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<70l> > > > tifa_libs::gen_ipowi<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<70l> > >(unsigned int):
✓ Branch 3 taken 1001000 times.
✓ Branch 4 taken 2 times.
std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<69l> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<69l> > > > tifa_libs::gen_ipowi<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<69l> > >(unsigned int):
✓ Branch 3 taken 1001000 times.
✓ Branch 4 taken 2 times.
std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > > tifa_libs::gen_ipowi<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > >(unsigned int):
✓ Branch 3 taken 1001000 times.
✓ Branch 4 taken 2 times.
std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > > tifa_libs::gen_ipowi<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > >(unsigned int):
✓ Branch 3 taken 1001000 times.
✓ Branch 4 taken 2 times.
 4004008 flt_ (u32, i, 0, n) ans[i] = _[i];
64 8 return ans;
65 8 }
66
67 } // namespace tifa_libs
68