HDU.5608.function(杜教筛)

(Description)

　　(n^2-3n+2=sum_{d|n}f(d))
　　求(sum_{i=1}^nf(i) mod 10^9+7).

(Solution)

　　参考.
　　设(g(n)=n^2-3n+2)，那么(f*I=g)。
　　如果狄利克雷卷积中左边的一个函数是待求前缀和的，而另外两个函数的前缀和比较好计算，那么就可以简化计算过程。
　　像之前一样，试着计算一下(sum_{i=1}^ng(i)): $$sum_{i=1}^ng(i)=sum_{i=1}^nsum_{d|i}f(d)=sum_{i=1}^nsum_{d=1}^{lfloorfrac{n}{i} floor}f(d)$$
　　而

　　（upd：好久没用，不知道博客园怎么改的Latex，不知道哪错了，复制到别的上看叭）
　　step2同之前，就是换做考虑因数贡献的值(sum_{i=1}^nsum_{d|i}f(frac{i}{d})=sum_{d=1}^nsum_{i=1}^{lfloorfrac{n}{d} floor}f(i))。
　　这样(sum_{i=1}^nf(i)=frac{n(n-1)(n-2)}{3}-sum_{i=2}^nsum_{d=1}^{lfloorfrac{n}{i} floor}f(d))。
　　预处理就用线筛和莫比乌斯反演 暴力枚举约数。（枚举到多少最适合我也不知道==经过二分，发现确实是6e5比较好...）

/*
注意：有μ所以会有负的！不能用Mod(x)，也不能直接取模(先+mod) 
*/
#include<map>
#include<cstdio>
#include<cctype>
#define gc() getchar()
typedef long long LL;
const int N=6e5+1,mod=1e9+7;

int n,mu[N+3],P[N>>1],f[N+3],cnt;
bool Not_P[N+3];
std::map<int,int> ref;

inline int read()
{
	int now=0;register char c=gc();
	for(;!isdigit(c);c=gc());
	for(;isdigit(c);now=now*10+c-'0',c=gc());
	return now;
}
#define Mod(x) x>=mod?x-=mod:0
void Init()
{
	mu[1]=1;
	for(int i=2;i<N;++i)
	{
		if(!Not_P[i]) P[++cnt]=i,mu[i]=-1;
		for(int j=1;j<=cnt&&i*P[j]<N;++j)
		{
			Not_P[i*P[j]]=1;
			if(!(i%P[j])) {mu[i*P[j]]=0; break;}
			mu[i*P[j]]=-mu[i];
		}
	}
	for(int i=1;i<N;++i)
	{
		int t=((LL)i*i%mod-3*i%mod+2+mod)%mod;
		for(int j=i;j<N;j+=i)
			(f[j]+=mu[j/i]*t%mod)%=mod;
//		WA:	f[j]+=mu[j/i]*t%mod, Mod(f[j]);
	}
	for(int i=1;i<N;++i) f[i]=((f[i]+f[i-1])%mod+mod)%mod;
//WA:for(int i=1;i<N;++i) sum[i]=sum[i-1]+f[i]%mod, Mod(sum[i]);
}
int FP(LL x,int k)
{
	LL t=1;
	for(;k;k>>=1,x=x*x%mod)
		if(k&1) t=t*x%mod;
	return t;
}
const int inv3=FP(3,mod-2);//333333336
int Calc(int n)
{
	if(n<N) return f[n];
	if(ref.count(n)) return ref[n];
	int ans=(1LL*n*(n-1)%mod*(n-2)%mod*inv3%mod);
	for(int las,i=2;i<=n;i=las+1)
		las=n/(n/i),ans-=1ll*(las-i+1)*Calc(n/i)%mod,ans%=mod;
	return ref[n]=(ans+mod)%mod;
}

int main()
{
	Init();
	for(int t=read();t--;)
	{
		int n=read();
		printf("%d
",Calc(n));
	}
	return 0;
}