题目大意：有$T(1\leqslant T\leqslant 10)$组数据，每组数据给你$A,B,C(0<A,B,C\leqslant 10^7)$，求$\sum\limits_{i=1}^A\sum\limits_{j=1}^B\sum\limits_{k=1}^C\varphi((i,j^2,k^3))\bmod 2^{30}$
题解：
$$\def \dsum{\displaystyle\sum\limits}\begin{align*}&\dsum_{i=1}^A\dsum_{j=1}^B\dsum_{k=1}^C\varphi((i,j^2,k^3))\\=&\dsum_{d=1}^A\varphi(d)\dsum_{i=1}^A\dsum_{j=1}^B\dsum_{k=1}^C[(i,j^2,k^3)=d]\\\end{align*}$$$$
\def \dsum{\displaystyle\sum\limits}令f(x)=\dsum_{i=1}^A\dsum_{j=1}^B\dsum_{k=1}^C[(i,j^2,k^3)=x]\\\begin{align*}F(x)&=\dsum_{x|p}f(p)\\ &=\dsum_{i=1}^A\dsum_{j=1}^B\dsum_{k=1}^C[x|(i,j^2,k^3)]\\ &=\dsum_{i=1}^A[x|i]\dsum_{j=1}^B[x|j^2]\dsum_{k=1}^C[x|j^3]\\&莫比乌斯反演得：\\f(x)&=\dsum_{x|k}\mu(\dfrac k x)F(k)\\ &=\dsum_{i=1}^A\mu(i)F(ix)\\ans&=\dsum_{d=1}^A\varphi(d)\dsum_{i=1}^A\mu(i)F(id)\\ &=\dsum_{T=1}^AF(T)\dsum_{d|T}\varphi(d)\mu(\dfrac T d)\\&由狄利克雷卷积得：\\ans&=\dsum_{T=1}^AF(T)(\mu*\varphi)(d)\end{align*}$$$$
狄利克雷卷积得(\mu*\varphi)(d)为积性函数\\\def \dsum{\displaystyle\sum\limits}令g(x)=\dsum_{d|T}\mu(d)\varphi(\dfrac T d)\\\begin{align*}g(1)&=1\\g(p)&=\mu(1)\varphi(p)+\mu(p)\varphi(1)\\ &=1\cdot(p-1)+(-1)\cdot1\\g(p^k)&=\mu(1)\varphi(p^k)\\ &+\mu(p)\varphi(p^{k-1})\\ &\qquad\vdots\\ &+\mu(p^k)\varphi(1)\\\because&\mu(p^k)当k\geqslant2时为0\\\therefore g(p^k)&=\mu(1)\varphi(p^k)+\mu(p)\varphi(p^{k-1})\\ &=p^k-k^{k-1}-(p^{k-1}-p^{k-2})\\ &=p^k-2p^{k-1}+p^{k-2}\\\therefore g(p^k)&=\begin{cases}1(k=0)\\p-2(k=1)\\(p-1)^2(k=2)\\p\cdot g(p^{k-1})(k\geqslant2)\\\end{cases}\end{align*}\\可以用线性筛来做$$$$
\def \dsum{\displaystyle\sum\limits}\def \dprod{\displaystyle\prod\limits}F(x)=\dsum_{i=1}^A[x|i]\dsum_{j=1}^B[x|j^2]\dsum_{k=1}^C[x|j^3]\\易得\dsum_{i=1}^A[x|i]=\left\lfloor\dfrac A x\right\rfloor\\考虑\dsum_{j=1}^B[x|j^2]:\\对x分解质因数\\令x=\dprod p_i^{c_i}\\令y_2(x)=\dprod p_i^{\left\lceil\dfrac{c_i}{2}\right\rceil}\\x|j^2\Rightarrow[y_2(x)|j]\\\therefore \dsum_{j=1}^B[x|j^2]=\left\lfloor\dfrac{B}{y_2(x)}\right\rfloor\\同理，令y_3(x)=\dprod p_i^{\left\lceil\dfrac{c_i}{3}\right\rceil}\\\therefore \dsum_{k=1}^C[x|j^3]=\left\lfloor\dfrac{B}{y_3(x)}\right\rfloor\\\therefore F(x)=\left\lfloor\dfrac A x\right\rfloor\left\lfloor\dfrac{B}{y_2(x)}\right\rfloor\left\lfloor\dfrac{B}{y_3(x)}\right\rfloor\\y_2(x),y_3(x)都可以线性筛$$卡点：无
C++ Code：
#include#define maxn 10000010#define mod 1073741823int Tim, A, B, C;int pl[maxn], ptot, g[maxn], f2[maxn], f3[maxn];int cnt[maxn];bool isp[maxn];inline int sqr(int x) {return x * x;}void sieve(int n) { g[1] = f2[1] = f3[1] = 1; for (int i = 2; i < n; i++) { if (!isp[i]) { pl[ptot++] = i; g[i] = i - 2; f2[i] = f3[i] = i; cnt[i] = 1; } for (int j = 0; j < ptot && pl[j] * i < n; j++) { int t = pl[j] * i; isp[t] = true; if (i % pl[j] == 0) { cnt[t] = cnt[i] + 1; int p = i / pl[j]; if (p % pl[j]) g[t] = g[p] * sqr(pl[j] - 1); else g[t] = g[i] * pl[j]; f2[t] = f2[i] * (cnt[t] & 1 ? pl[j] : 1); f3[t] = f3[i] * (cnt[t] % 3 == 1 ? pl[j] : 1); break; } cnt[t] = 1; g[t] = g[i] * g[pl[j]]; f2[t] = f2[i] * f2[pl[j]]; f3[t] = f3[i] * f3[pl[j]]; } }}int main() { sieve(maxn); scanf("%d", &Tim); while (Tim --> 0) { scanf("%d%d%d", &A, &B, &C); int ans = 0; for (int i = 1; i <= A; i++) ans += g[i] * (A / i) * (B / f2[i]) * (C / f3[i]); printf("%d\n", ans & mod); } return 0;}