bzoj 4804 欧拉心算

~{→看不见LaTex格式的Dalao们请刷新本页Thanks♪(･ω･)ﾉ←}~

2019寒假集训题

C.欧拉心算

题面

给出一个数字N，求$\sum_{i=1}^n\sum_{j=1}^n\phi(gcd(i,j))$。

---

Input

第一行为一个正整数$T$，表示数据组数。

接下来$T$行为询问，每行包含一个正整数$N$。

---

Output

按读入顺序输出答案。

---

Sample Input

1

10

---

Sample Output

136

---

Hint

$T\leq5000,N\leq10^7$

---

解析

莫比乌斯反演一波可得：

$$Ans=\sum_{i=1}^n\sum_{j=1}^n\phi(gcd(i,j))=\sum_{i=1}^n\phi(i)\sum_{d=1}^{\lfloor\frac ni\rfloor}\mu(d)\lfloor\frac n{id}\rfloor^2$$

令$g(n)=\sum_{d=1}^n\mu(d)\lfloor\frac nd\rfloor^2​$

因为$\lfloor\frac nd\rfloor-\lfloor\frac {n-1}d\rfloor=1$成立当且仅当$d|n$

那么$g(n)=g(n-1)+\sum_{d|n}\mu(d)(2\frac {n}d-1)$

因为$\sum_{d|n}\frac {\mu(d)}d=\frac {\phi(n)}n$

$g(n)=g(n-1)+2\phi(d)-[n==1]​$

于是有$Ans=\sum_{i=1}^n\phi(i)g(\lfloor\frac ni\rfloor)$

该算法时间复杂度为$O(T\sqrt N)$

---

#include<bits/stdc++.h>
using namespace std;
int read()
{
	int x = 0, w = 0;
	char ch = 0;
	while (!isdigit(ch)) {w |= ch == '-'; ch = getchar();}
	while (isdigit(ch)) {x = (x << 3) + (x << 1) + ch - '0'; ch = getchar();}
	return w ? -x : x;
}
const int N = 1e7 + 10;
int p[N], cnt, q[5010], T;
long long phi[N], g[N];
bool notprime[N];
void work(int m, long long ans = 0)
{
	for (int i = 1, ne; i <= m; i = ne + 1)
	{
		ne = m / (m / i);
		ans += (phi[ne] - phi[i - 1]) * g[m / i];
	}
	cout << ans << endl;
}
void Prime()
{
	phi[1] = g[1] = 1, notprime[1] = 1;
	for (int i = 2; i <= 10000000; ++i)
	{
		if (!notprime[i])
		{
			p[++cnt] = i;
			phi[i] = i - 1;
		}
		for (int j = 1; j <= cnt && i * p[j] <= 10000000; ++j)
		{
			notprime[i * p[j]] = 1;
			if (i % p[j] == 0)
			{
				phi[i * p[j]] = phi[i] * p[j];
				break;
			}
			else phi[i * p[j]] = phi[i] * (p[j] - 1);
		}
		g[i] = g[i - 1] + 2 * phi[i];
	}
	for (int i = 2; i <= 10000000; ++i) phi[i] += phi[i - 1];
}
int main()
{
	T = read();
	Prime();
	while (T--) work(read());
	return 0;
}