src/nt/mfsum/sqrfree_cnt/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../../math/iroot/kth/lib.hpp" | ||
| 4 | #include "../../../math/iroot/sqrt/lib.hpp" | ||
| 5 | #include "../../lsieve/func/lib.hpp" | ||
| 6 | #include "../../lsieve/impl1/lib.hpp" | ||
| 7 | |||
| 8 | namespace tifa_libs { | ||
| 9 | |||
| 10 | 22 | CEXP u64 sqrfree_cnt(u64 n, veci mu) NE { | |
| 11 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 22 times.
|
22 | retif_((n <= 3) [[unlikely]], n); |
| 12 | 22 | cu32 I = (u32)min(ikth_root(n, 5) * 2, ikth_root(n / 4, 3)), D = isqrt(n / I); | |
| 13 | 22 | u64 ans = 0; | |
| 14 |
2/2✓ Branch 0 taken 112710631 times.
✓ Branch 1 taken 22 times.
|
112710653 | flt_ (u32, i, 1, D + 1) |
| 15 |
2/2✓ Branch 1 taken 68519973 times.
✓ Branch 2 taken 44190658 times.
|
112710631 | if (mu[i]) ans += (u64)mu[i] * (n / ((u64)i * i)); |
| 16 |
2/2✓ Branch 2 taken 112710631 times.
✓ Branch 3 taken 22 times.
|
112710653 | flt_ (u32, i, 1, D + 1) mu[i] += mu[i - 1]; |
| 17 | 22 | veci mu_large(I + 1); | |
| 18 |
2/2✓ Branch 0 taken 89863 times.
✓ Branch 1 taken 22 times.
|
89885 | for (u32 i = I - 1; i >= 1; --i) { |
| 19 | 89863 | cu32 xi = isqrt(n / i), h = isqrt(xi), tlim = 2 * h - (h == xi / h); | |
| 20 |
2/2✓ Branch 0 taken 713987685 times.
✓ Branch 1 taken 713897689 times.
|
1427885374 | auto f = [xi, h, tlim](u32 i) NE -> u32 { retif_((i < h), i + 1, u32(f64(xi) / (2 * h - (tlim & 1) - i))); }; |
| 21 | 89863 | i64 sum = 1; | |
| 22 |
2/2✓ Branch 0 taken 713942687 times.
✓ Branch 1 taken 89863 times.
|
714032550 | for (u32 t = 1, l = 1; t < tlim; ++t) { |
| 23 | 713942687 | cu32 r = f(t), q = f(tlim - t - 1); | |
| 24 |
2/2✓ Branch 0 taken 713886328 times.
✓ Branch 1 taken 56359 times.
|
713942687 | sum -= i64(r - l) * (q <= D ? mu[q] : mu_large[(u64)i * r * r]), l = r; |
| 25 | } | ||
| 26 | 89863 | ans += u64(mu_large[i] = (i32)sum); | |
| 27 | } | ||
| 28 | 22 | return ans - u64(i64(I - 1) * mu[D]); | |
| 29 | 22 | } | |
| 30 | 25 | CEXP u64 sqrfree_cnt(u64 n) NE { | |
| 31 |
2/2✓ Branch 0 taken 3 times.
✓ Branch 1 taken 22 times.
|
25 | retif_((n <= 3) [[unlikely]], n); |
| 32 | 22 | cu32 I = (u32)min(ikth_root(n, 5) * 2, ikth_root(n / 4, 3)), D = isqrt(n / I); | |
| 33 | 22 | return sqrfree_cnt(n, lsieve<ls_mu>(D + 1).mu); | |
| 34 | } | ||
| 35 | |||
| 36 | } // namespace tifa_libs | ||
| 37 |