Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom7月前

04/5
13:59
筛法 莫比乌斯反演

[bzoj 4804] 欧拉心算

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

给出一个数字N

\sum_{i = 1} ^ n \sum_{j=1}^n\phi (gcd(i,j))

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

第一行为一个正整数T,表示数据组数。
接下来T行为询问,每行包含一个正整数N。
T<=5000,N<=10^7

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

按读入顺序输出答案。

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

1
10

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

136

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

莫比乌斯反演一下得到  Ans = \sum_{d=1}^n\lfloor\frac{n}{d} \rfloor^2 \sum_{k | d}\phi(k)\mu(\frac{d}{k})

显然后面的那个东西是两个积性函数卷在一起肯定也是一个积性函数 可以用线性筛解决

f(nx^2) = \sum_{k | n} (\mu(kx)\phi(\frac{n}{k} * x) + \mu(\frac{n}{k})\phi(kx^2))

f(nx^2) = \sum_{k | n} (-(x-1)\mu(k)\phi(\frac{n}{k}) +x(x - 1)\mu(\frac{n}{k})\phi(k)) = f(n)*(x-1)^2

f(nx^y) = \sum_{k | n} (\mu(kx)\phi(\frac{n}{k} * x^{y - 1}) + \mu(\frac{n}{k})\phi(kx^y))

f(nx^y) = \sum_{k | n} (x\mu(kx)\phi(\frac{n}{k} * x^{y - 2}) + x\mu(\frac{n}{k})\phi(kx^{y-1}))=f(nx^{y-1})*x \\\ (y > 2)

根据这两个式子线性筛然后枚举商计算就可以了

 

[bzoj 4804] 欧拉心算