test/cpv_local/nt/lsieve2.bzoj4407.cpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | // competitive-verifier: LOCALCASE test/cpv_local/_data/bzoj/4407 | ||
| 2 | |||
| 3 | #include "../../../src/math/ds/mint/ms/lib.hpp" | ||
| 4 | #include "../../../src/math/qpow/basic/lib.hpp" | ||
| 5 | #include "../../../src/nt/lsieve/impl2/lib.hpp" | ||
| 6 | |||
| 7 | using namespace tifa_libs; | ||
| 8 | using std::cin, std::cout; | ||
| 9 | using mint = mint_ms<1'000'000'000 + 7>; | ||
| 10 | |||
| 11 | 10 | int main() { | |
| 12 | u32 t, k; | ||
| 13 |
2/4✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 10 times.
✗ Branch 5 not taken.
|
10 | cin >> t >> k; |
| 14 |
2/4✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 10 times.
✗ Branch 5 not taken.
|
30 | vecu ns(t), ms(t); |
| 15 |
2/2✓ Branch 0 taken 20000 times.
✓ Branch 1 taken 10 times.
|
20010 | flt_ (u32, i, 0, t) { |
| 16 |
2/4✓ Branch 2 taken 20000 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 20000 times.
✗ Branch 7 not taken.
|
20000 | cin >> ns[i] >> ms[i]; |
| 17 |
2/2✓ Branch 2 taken 9939 times.
✓ Branch 3 taken 10061 times.
|
20000 | if (ns[i] > ms[i]) std::swap(ns[i], ms[i]); |
| 18 | } | ||
| 19 | 10 | u32 n = std::ranges::max(ns); | |
| 20 | 10 | lsieve2 ls(n); | |
| 21 | static mint pk, lst; | ||
| 22 | vec<mint> g = ls.template run<mint>( | ||
| 23 | 3445026 | [&](u32 p, u32 e) -> mint { | |
| 24 |
2/2✓ Branch 0 taken 3440767 times.
✓ Branch 1 taken 4259 times.
|
3445026 | if (e == 1) return lst = (pk = qpow<mint>(p, k)) - 1; |
| 25 | 4259 | else return lst *= pk; | |
| 26 | 10 | }); | |
| 27 |
1/2✓ Branch 4 taken 10 times.
✗ Branch 5 not taken.
|
10 | std::inclusive_scan(begin(g), end(g), begin(g)); |
| 28 |
2/2✓ Branch 0 taken 20000 times.
✓ Branch 1 taken 10 times.
|
20010 | flt_ (u32, i, 0, t) { |
| 29 | 20000 | mint res = 0; | |
| 30 |
2/2✓ Branch 2 taken 83299165 times.
✓ Branch 3 taken 20000 times.
|
83319165 | for (u32 n = ns[i], m = ms[i], l = 1, r, d1, d2; l <= n; l = r + 1) { |
| 31 | 83299165 | r = std::min(n / (d1 = n / l), m / (d2 = m / l)); | |
| 32 | 83299165 | res += (g[r] - g[l - 1]) * d1 * d2; | |
| 33 | } | ||
| 34 |
2/4✓ Branch 2 taken 20000 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 20000 times.
✗ Branch 6 not taken.
|
20000 | cout << res.val() << '\n'; |
| 35 | } | ||
| 36 | 10 | } | |
| 37 |