HDU 5942 && 2016CCPC杭州 J: Just a Math Problem（莫比乌斯函数）

题意：

已知f(k)为k的质因子数

求∑2^f(k)  (1<=k<=n)

发现现在做什么题程序都特别慢。。。14866/15000ms真刺激

因为f(k)是k的质因子个数

那么2^f(k)相当于k的每个质因子取或不取构成2^f(k)个莫比乌斯函数值为±1的数

那么有

又因为莫比乌斯函数性质

所以可以将右边那个求和拆开

再将式子转为计算每个u(k)的贡献：

很显然当k>sqrt(n)时右边的求和为0，所以左边的求和只用求到sqrt(n)就好了

然后右边的式子可以通过枚举约数在logn*sqrt(n)的复杂度求出来，线性预处理前sqrt(n)个莫比乌斯函数也不成问题

这样就可以直接暴力计算了，总体复杂度O(logn*sqrt(n))

#include<stdio.h>
#define LL long long
#define mod 1000000007
LL cnt, pri[80025], flag[1000025] = {1,1}, mu[1000005] = {0,1}, F[1000005];
LL S(LL n)
{
	LL L, R, sum = 0;
	if(n<=1000000 && F[n]!=0)
		return F[n];
	L = 1;
	while(L<=n)
	{
		R = n/(n/L);
		sum += n/L*(R-L+1);
		L = R+1;
	}
	sum %= mod;
	if(n<=1000000)
		F[n] = sum;
	return sum;
}
int main(void)
{
	LL T, i, j, n, ans, cas = 1;
	for(i=2;i<=1000005;i++)
	{
		if(flag[i]==0)
		{
			pri[++cnt] = i;
			mu[i] = -1;
		}
		for(j=1;j<=cnt&&i*pri[j]<=1000005;j++)
		{
			flag[i*pri[j]] = 1;
			if(i%pri[j]==0)
			{
				mu[i*pri[j]] = 0;
				break;
			}
			mu[i*pri[j]] = -mu[i];
		}
	}
	scanf("%lld", &T);
	while(T--)
	{
		ans = 0;
		scanf("%lld", &n);
		for(i=1;i*i<=n;i++)
		{
			if(mu[i]==0)
				continue;
			ans = ((ans+mu[i]*S(n/i/i))%mod+mod)%mod;
		}
		printf("Case #%lld: %lld\n", cas++, ans);
	}
	return 0;
}