题面:
一句话题意:
给出 (k) 组询问,每次给你一个 (n) ,让你回答 (displaystylesum_{i=1}^{n}sum_{j=1}^{n}phi(gcd(i,j))
题解
下面,又到了我们的颓柿子时间啦。
我们要求的是这个柿子:
(displaystylesum_{i=1}^{n}sum_{j=1}^{n}phi(gcd(i,j))
先枚举一个 (d) 可得:
(displaystylesum_{d=1}^{n}phi(d) sum_{i=1}^{n}sum_{j=1}^{n} [gcd(i,j) == d])
后面的那两个求和柿子可以提出一个 (d) 来,变成:
(displaystylesum_{d=1}^{n} phi(d) sum_{i=1}^{nover d}sum_{j=1}^{nover d} [gcd(i,j) == 1])
后面的柿子有没有觉得有点熟悉?
如果你做过 仪仗队 ,你就会一眼把他秒了。
我们有一个等式: (displaystylesum_{i=1}^{n}sum_{j=1}^{n}[gcd(i,j) == 1] = sum_{i=1}^{n}2 imes phi(i) - 1)
具体证明:
首先对于一个 (i), 与他互质的个数 是 (phi(i)) ,又因为 (i,j) 和 (j, i)这两个数对算两个,所以要乘二,减一则是要减去算重复的1.
对于 (i leq j) 的情况有 (displaystylesum_{i=1}^{n} sum_{j=1}^{i}[gcd(i,j) == 1] = sum_{i=1}^{n} phi(i))
对于 (i >= j) 的情况同理,最后在减去重复计算的 1
把这个等式代回原来的柿子,可以化简为:
(displaystylesum_{d=1}^{n}phi(d) sum_{i=1}^{n over d} 2 imes phi(i) - 1)
他还可以化为
(displaystyle(sum_{d=1}^{n} phi(d) (2 imes sum[{n over d}])) - sum[n]))
对后面的求和柿子,可以预处理出来 (phi) 函数的前缀和。,在用一下数论分块,枚举每个 (d) 即可。
Code
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define LL long long
const int N = 1e7+10;
int t,n,m,tot;
int prime[N],phi[N];
LL sum[N];
bool check[N];
inline int read()
{
int s = 0,w = 1; char ch;
while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
while(ch >= '0' && ch <= '9'){s =s * 10+ch - '0'; ch = getchar();}
return s * w;
}
void YYCH()
{
phi[1] = 1;
for(int i = 2; i <= N-5; i++)//预处理φ函数值
{
if(!check[i])
{
prime[++tot] = i;
phi[i] = i-1;
}
for(int j = 1; j <= tot && i * prime[j] <= N-5; j++)
{
check[i * prime[j]] = 1;
if(i % prime[j] == 0)
{
phi[i * prime[j]] = phi[i] * prime[j];
}
else
{
phi[i * prime[j]] = phi[i] * phi[prime[j]];
}
}
}
for(int i = 1; i <= N-5; i++)//求前缀和
{
sum[i] = sum[i-1] + phi[i];
}
}
LL slove(int n)
{
LL res = 0;
for(int l = 1,r; l <= n; l = r + 1)//数论分块
{
r = n/(n/l);
res += 1LL * 2 * (sum[n/l]) * (sum[r]-sum[l-1]);
}
res -= sum[n];
return res;
}
int main()
{
t = read(); YYCH();
while(t--)
{
n = read();
printf("%lld
",slove(n));
}
return 0;
}