[hdu6428]Problem C. Calculate

题目大意：有$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 <cstdio>

#define maxn 10000010

#define mod 1073741823

int 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;

}

巴特西

[hdu6428]Problem C. Calculate

最新文章

热门文章