【bzoj4804】欧拉心算莫比乌斯反演+莫比乌斯函数性质+线性筛

Description

给出一个数字N

求$\sum_{i=1}^{n}\sum_{j=1}^{n}\varphi(gcd(i,j))$

Input

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

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

T<=5000,N<=10^7

Output

按读入顺序输出答案。

Sample Input

1

10

Sample Output

136

sol

这种题，八成和欧拉函数或者莫比乌斯函数有关......

那就推式子：

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

$=\sum_{d=1}^{n}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}\varphi(d)\sum_{e|i,e|j}\mu(e)$

$=\sum_{d=1}^{n}\varphi(d)\sum_{e=1}^{\lfloor\frac{n}{d}\rfloor}\mu(e)\sum_{i=1}^{\lfloor\frac{n}{de}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{de}\rfloor}1$

$=\sum_{d=1}^{n}\varphi(d)\sum_{e=1}^{\lfloor\frac{n}{d}\rfloor}\mu(e)\lfloor\frac{n}{de}\rfloor^2$

$=\sum_{T=1}^{n}\lfloor\frac{n}{T}\rfloor^2\sum_{d|T}\varphi(\frac{T}{d})\mu(d)$

前面的那个直接分块即可，后面的冷静分析一下：

“看到$\mu$就想到积性函数，就想到质因数分解，就想到消去$>$2的幂的贡献，OIer的思想唯有在这一层能如此跃进 ”

我们把T分解质因数之后，对于每个质数$p_i$的$q_i$次幂单独计算，最后再乘起来。

由于乘数里面有$\mu$，所以大于2的幂次产生的贡献可以忽略，对于每个质数，后面这个式子就能够直接推出公式，具体地：

$if\quad qi=0\quad f(p_i)=1$

$if\quad q_i=1\quad f(p_i)=p_i-2$

$if\quad q_i=2\quad f(p_i)=(p_i-1)^2$

$else\quad f(p_i)=pi^{qi-2}(p_i-1)^2$

那么这个就可以线性筛了。

然后就没有了。

Code

#include <cstdio>

#define ll long long

int ls,n,T,vis[10000005],pri[10000005],tot;ll s[10000005];

void shai()

{

	s[1]=1;for(int i=2;i<=1e7;i++)

	{

		if(!vis[i]) pri[++tot]=i,s[i]=i-2;

		for(int j=1;j<=tot&&i*pri[j]<=1e7;j++)

		{

			vis[i*pri[j]]=1;

			if(i%pri[j]==0)

			{

				if(i/pri[j]%pri[j]==0) s[i*pri[j]]=s[i]*pri[j];

				else s[i*pri[j]]=s[i/pri[j]]*(pri[j]-1)*(pri[j]-1);

				break;

			}

			s[i*pri[j]]=s[i]*(pri[j]-2);

		}

	}

	for(int i=1;i<=1e7;i++) s[i]+=s[i-1];

}

ll cal(int n){ll ans=0;for(int i=1;i<=n;i=ls+1) ls=n/(n/i),ans+=(s[ls]-s[i-1])*(n/i)*(n/i);return ans;}

int main(){for(shai(),scanf("%d",&T);T--;printf("%lld\n",cal(n))) scanf("%d",&n);}

巴特西

【bzoj4804】欧拉心算莫比乌斯反演+莫比乌斯函数性质+线性筛

Description

Input

Output

Sample Input

Sample Output

sol

Code

最新文章

热门文章

巴特西

【bzoj4804】欧拉心算 莫比乌斯反演+莫比乌斯函数性质+线性筛

Description

Input

Output

Sample Input

Sample Output

sol

Code

最新文章

热门文章

【bzoj4804】欧拉心算莫比乌斯反演+莫比乌斯函数性质+线性筛