#P3739. DZY loves math VIII

    ID: 2951 传统题 3000ms 512MiB 尝试: 279 已通过: 71 难度: 7 上传者: 标签>CF2300提高+/省选-莫比乌斯函数莫比乌斯反演线性筛最小质因子预处理全子集枚举增量维护一维前缀和零贡献剪枝

DZY loves math VIII

题目描述

对每个询问给出的正整数 nn,求

$$\sum_{i=1}^{n}\sum_{j=1}^{i} \mu\!\left(\operatorname{lcm}(i,j)^{\gcd(i,j)}\right).$$

μ\mu 为莫比乌斯函数。μ(1)=1\mu(1)=1。如果 xx 能被某个素数的平方整除,μ(x)=0\mu(x)=0。否则若 xx 有 kk 个不同的素因子,则 μ(x)=(−1)k\mu(x)=(-1)^k。

输入格式

第一行一个整数 TT(1≤T≤1031\le T\le10^3),表示询问组数。接下来 TT 行,每行一个正整数 nn(1≤n≤1071\le n\le10^7)。

输出格式

每个询问输出一行一个整数,表示该求和的值。

样例

1
2
0

原 BZOJ 题面及求和公式