HDU-5608

题意：$G(n)=n^2−3n+2=\sum_{d|n}F(d)$，求$\sum_1^nF(i)$

反演得到：$F(n)=\sum_{d|n}\mu(d)G(\frac{n} {d})$

则$\sum_1^nF(i)=\sum_i\sum_{d|i}\mu(d)G(\frac{i} {d})$

$\sum_1^nF(i)=\sum_{i=1}^{n}G(i)\sum_{j=1}^{\lfloor \frac{n} {i}\rfloor }\mu(j)$

问题就是要快速求$G(i)$前缀和和$\mu(i)$前缀和

第一个是$O(1)$求，第二个是杜教筛

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

const int N=5e6+10,P=1e9+7;

ll qpow(ll x,ll k=P-2) {
	ll res=1;
	for(;k;k>>=1,x=x*x%P) if(k&1) res=res*x%P;
	return res;
}

const int Inv6=qpow(6);

int n;
char notpri[N],w[N];
int pri[N/4],pc,Sw[N];
map <int,int> M;

int SumG(int n){ // O(1)求出G函数的前缀和
	ll ans=1ll*n*(n+1)%P*(2*n+1)%P*Inv6%P;
	ans=(ans-3ll*n*(n+1)/2%P+2*n)%P;
	ans=(ans%P+P)%P;
	return ans;
}

int Sumw(int n){ // 杜教筛求mobius函数前缀和
	if(n<N) return Sw[n];
	if(M.count(n)) return M[n];
	int ans=1;
	for(int i=2,j;i<=n;i=j+1) {
		j=n/(n/i);
		ans-=(j-i+1)*Sumw(n/i);
	}

	return M[n]=ans;
}

int SumF(int n){ // 答案
	int ans=0;
	for(int i=1,j;i<=n;i=j+1) {
		j=n/(n/i);
		ans=(ans+1ll*(SumG(j)-SumG(i-1))*Sumw(n/i))%P;
	}
	ans=(ans%P+P)%P;
	return ans;
}

int main(){
	w[1]=1;
	rep(i,2,N-1) {
		if(!notpri[i]) pri[++pc]=i,w[i]=-1;
		for(int j=1;j<=pc && 1ll*i*pri[j]<N;++j) {
			notpri[i*pri[j]]=1;
			if(i%pri[j]==0) {
				w[i*pri[j]]=0;
				break;
			}
			w[i*pri[j]]=-w[i];
		}
	}
	rep(i,1,N-1) Sw[i]=Sw[i-1]+w[i];
	rep(kase,1,rd()) printf("%d\n",SumF(rd()));
}