library_checker/math/
sum_of_totient_function.rs

1#[doc(no_inline)]
2pub use competitive::{
3    algebra::{AddMulOperation, AdditiveOperation, ArrayOperation},
4    math::QuotientArray,
5    num::mint_basic::MInt998244353,
6};
7use competitive::{num::One, prelude::*};
8
9type M = MInt998244353;
10
11#[verify::library_checker("sum_of_totient_function")]
12pub fn sum_of_totient_function(reader: impl Read, mut writer: impl Write) {
13    let s = read_all_unchecked(reader);
14    let mut scanner = Scanner::new(&s);
15    scan!(scanner, n: u64);
16    let mut s = 1;
17    let mut pp = 0;
18    let mut pc = 0;
19    let inv2 = M::new(2).inv();
20    let qa = QuotientArray::from_fn(n, |i| [M::from(i), M::from(i) * M::from(i + 1) * inv2])
21        .map(|[x, y]| [x - M::one(), y - M::one()])
22        .lucy_dp::<ArrayOperation<AdditiveOperation<_>, 2>>(|[x, y], p| [x, y * M::from(p)])
23        .map(|[x, y]| y - x)
24        .min_25_sieve::<AddMulOperation<_>>(|p, c| {
25            if pp != p || pc > c {
26                pp = p;
27                pc = 1;
28                s = p - 1;
29            }
30            while pc < c {
31                pc += 1;
32                s *= p;
33            }
34            M::from(s)
35        });
36    writeln!(writer, "{}", qa[n]).ok();
37}

library_checker/math/sum_of_totient_function.rs

library_checker/math/
sum_of_totient_function.rs