【模板】积性函数前缀和Ⅰ ‖ 卷积性质：杜教筛

题号：NC232572
时间限制：C/C++/Rust/Pascal 5秒，其他语言10秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 对于给定的整数 $n$ ，求解欧拉函数 $^\texttt{[1]}$ $\varphi(i)$ 和莫比乌斯函数 $^\texttt{[2]}$ $\mu(i)$ 的前 $n$ 项和。

$\hspace{15pt}$ 换句话说，计算 $\sum\limits_{i=1}^n\varphi(i)$ 和 $\sum\limits_{i=1}^n \mu(i)$ 。

【名词解释】
$\hspace{15pt}$ 欧拉函数 $^\texttt{[1]}$ ：指整数 $1,2,\dots,x$ 中，与 $x$ 互质的数的个数，记为 $\varphi(x)$ 。
$\hspace{15pt}$ 莫比乌斯函数 $^\texttt{[2]}$ ：定义为 $\mu(x) = \begin{cases}<br /> 1 & \text{若 } x = 1<br />\\ 0 & \text{若 } x \text{ 有大于 } 1 \text{ 的平方数因数}<br />\\ (-1)^k & \text{若 } x \text{ 无平方数因数，且 } x = \textrm{Prime}_1 \times \textrm{Prime}_2 \times \cdots \times \textrm{Prime}_k<br />\end{cases}$ 。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

在一行上输入一个整数 ，表示待查询的数字。

输出描述:

对于每一组测试数据，新起一行输出两个整数，表示欧拉函数的前  项和、莫比乌斯函数的前  项和。

示例1

输入

复制

输出

复制

备注:

本题已于下方时间节点更新，请注意题解时效性：
1. 2025-11-30 优化题面文本与格式。模板题为便于测试，将时间限制扩充至 5s，空间限制扩充至 1024MB。