题目描述

有N2−3N+2=∑d∣Nf(d)N^2-3N+2=\sum_{d|N} f(d)N2−3N+2=∑d∣Nf(d)

求∑i=1Nf(i)\sum_{i=1}^{N} f(i)∑i=1Nf(i) mod 109+7~mod~10^9+7 mod 109+7

1<=T<=5001<=N<=1091<=T<=500\\1<=N<=10^91<=T<=5001<=N<=109

只有最多555组数据N>106N>10^6N>106

题目分析

f(n)=n2−3n+2−∑d∣n,d<nf(d)∴S(n)=∑i=1n(i2−3i+2−∑d∣i,d<if(d)) =∑i=1ni2−3∑i=1ni+2n−∑k=2n∑d=1⌊nk⌋f(d) =∑i=1ni2−3∑i=1ni+2n−∑k=2nS(⌊nk⌋) =n(n+1)(n−4)3+2n−∑k=2nS(⌊nk⌋)
f(n)=n^2-3n+2-\sum_{d|n,d<n}f(d)\\
\therefore S(n)=\sum_{i=1}^n(i^2-3i+2-\sum_{d|i,d<i}f(d))\\
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =\sum_{i=1}^ni^2-3\sum_{i=1}^ni+2n-\sum_{k=2}^n\sum_{d=1}^{\lfloor\frac nk\rfloor}f(d)\\
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =\sum_{i=1}^ni^2-3\sum_{i=1}^ni+2n-\sum_{k=2}^nS({\lfloor\frac nk\rfloor})\\
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =\frac {n(n+1)(n-4)}3+2n-\sum_{k=2}^nS({\lfloor\frac nk\rfloor})
f(n)=n2−3n+2−d∣n,d<n∑f(d)∴S(n)=i=1∑n(i2−3i+2−d∣i,d<i∑f(d)) =i=1∑ni2−3i=1∑ni+2n−k=2∑nd=1∑⌊kn⌋f(d) =i=1∑ni2−3i=1∑ni+2n−k=2∑nS(⌊kn⌋) =3n(n+1)(n−4)+2n−k=2∑nS(⌊kn⌋)

如此一来就可以杜教筛了,然而仅仅这样还是会T,于是我们在想一想如何筛出前面一部分的fff值

令g(n)=n2−3n+2g(n)=n^2-3n+2g(n)=n2−3n+2,根据莫比乌斯反演

∴f(n)=∑d∣nμ(⌊nd⌋)g(d)
\therefore f(n)=\sum_{d|n}\mu(\lfloor\frac nd\rfloor)g(d)
∴f(n)=d∣n∑μ(⌊dn⌋)g(d)

于是用Θ(106ln(106))\Theta (10^6ln(10^6))Θ(106ln(106))筛出前10610^6106项就行了

总时间复杂度Θ(106ln(106)+T+5n23)\Theta(10^6ln(10^6)+T+5n^{\frac 23})Θ(106ln(106)+T+5n32)

AC code:

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <map>

using namespace std;

const int MAXN = 1000001;

const int mod = 1e9+7;

const int inv3 = 333333336;

inline int g(int n)

{

	return (1ll * n * n % mod - 3ll * n % mod + 2) % mod;

}

int Prime[MAXN], Cnt, mu[MAXN], f[MAXN];

bool IsnotPrime[MAXN];

void init()

{

	mu[1] = 1;

	for(int i = 2; i < MAXN; ++i)

	{

		if(!IsnotPrime[i]) Prime[++Cnt] = i, mu[i] = -1;

		for(int j = 1; j <= Cnt && i * Prime[j] < MAXN; ++j)

		{

			IsnotPrime[i * Prime[j]] = 1;

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

			{

				mu[i * Prime[j]] = 0;

				break;

			}

			mu[i * Prime[j]] = -mu[i];

		}

	}

	for(int i = 1; i < MAXN; ++i)

		for(int j = i; j < MAXN; j+=i)

			f[j] = (f[j] + 1ll * mu[j/i] * g(i) % mod) % mod;

	for(int i = 1; i < MAXN; ++i) f[i] = (f[i-1] + f[i]) % mod;

}

map<int,int>F;

inline int solve(int n)

{

	if(n < MAXN) return f[n];

	if(F.count(n)) return F[n];

	int ret = (1ll * n * (n+1) % mod * (n-4) % mod * inv3 % mod + 2ll*n%mod) % mod;

	for(int i = 2, j; i <= n; i=j+1)

	{

		j = n/(n/i);

		ret = (ret - 1ll * (j-i+1) * solve(n/i) % mod) % mod;

	}

	return F[n]=ret;

}

int main()

{

	init();

	int T, n;

	scanf("%d", &T);

	while(T--)

	{

		scanf("%d", &n);

		printf("%d\n", (solve(n)+mod)%mod);

	}

}

巴特西

[HDU 5608]Function(莫比乌斯反演 + 杜教筛)

题目描述

题目分析

AC code:

最新文章

热门文章