Skip to main content

library_checker/number_theory/
sum_of_totient_function.rs

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