数论分块例题

链接：F-日常诈骗签到题_喜迎暑假多校联赛第一场 (nowcoder.com)

题意：给定 n ，求 ∑ i = 1 n ∑ j = 1 i ∑ d = 1 j ⌊ n i ⌋ μ ( d ) [ d ∣ i ] ] [ d ∣ j ] sum_{i=1}^{n}sum_{j=1}^{i}sum_{d=1}^{j}lfloor frac{n}{i} rfloor mu(d) [d|i]][d|j] ∑i=1n∑j=1i∑d=1j⌊in⌋μ(d)[d∣i]][d∣j] 。

题解：首先改变最外层的枚举，先枚举 d ，则原式子转化为 ∑ d = 1 n ∑ d ∣ i n ∑ d ∣ j i μ ( d ) ⌊ n i ⌋ sum_{d=1}^{n}sum_{d|i}^{n}sum_{d|j}^{i}mu(d) lfloor frac{n}{i} rfloor ∑d=1n∑d∣in∑d∣jiμ(d)⌊in⌋ ，将 μ ( d ) mu(d) μ(d) 提到最前边， ∑ d = 1 n μ ( d ) ∑ d ∣ i n ⌊ n i ⌋ ∑ d ∣ j i 1 sum_{d=1}^{n}mu(d) sum_{d|i}^{n} lfloor frac{n}{i} rfloor sum_{d|j}^{i}1 ∑d=1nμ(d)∑d∣in⌊in⌋∑d∣ji1，则最后的 j 可化掉为 ∑ d = 1 n μ ( d ) ∑ d ∣ i n ⌊ n i ⌋ ⌊ i d ⌋ sum_{d=1}^{n}mu(d) sum_{d|i}^{n} lfloor frac{n}{i} rfloor lfloorfrac{i}{d} rfloor ∑d=1nμ(d)∑d∣in⌊in⌋⌊di⌋，此时已经将单次询问的复杂度由最初的 O ( n 3 ) O(n^3) O(n3) 缩小为 O ( n l o g ( n ) ) O(nlog(n)) O(nlog(n)) 了。但是对于多组数据而言是不够的。

我们再次改变枚举的顺序，改为枚举 i，则原式子可化为 ∑ i = 1 n ⌊ n i ⌋ ∑ d ∣ i μ ( d ) ⌊ i d ⌋ sum_{i=1}^{n} lfloor frac{n}{i} rfloor sum_{d|i} mu(d) lfloor frac{i}{d} rfloor ∑i=1n⌊in⌋∑d∣iμ(d)⌊di⌋，发现对于 ∑ d ∣ i μ ( d ) ⌊ i d ⌋ sum_{d|i} mu(d) lfloor frac{i}{d} rfloor ∑d∣iμ(d)⌊di⌋ 是可以预处理的，枚举 d，对于其倍数的位置都会加上 μ ( d ) ⌊ i d ⌋ mu(d) lfloor frac{i}{d} rfloor μ(d)⌊di⌋，i 为 d 的倍数。然后将每个 i 的答案统计前缀和，因此在计算时便可以通过数论分块求 ∑ i = 1 n ⌊ n i ⌋ ∑ d ∣ i μ ( d ) ⌊ i d ⌋ sum_{i=1}^{n} lfloor frac{n}{i} rfloor sum_{d|i} mu(d) lfloor frac{i}{d} rfloor ∑i=1n⌊in⌋∑d∣iμ(d)⌊di⌋ , 复杂度是 O ( n ) O(sqrt{n}) O(n ) 。则总的复杂度是 O ( T n + n l o g ( n ) ) O(Tsqrt{n}+nlog(n)) O(Tn +nlog(n))。可以通过此题。（打表找规律 O(1) 输出也可以，答案为 ( 1 + n ) ∗ n 2 frac{(1+n)*n}{2} 2(1+n)∗n）。

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include
#include
#include
#include
#include
#include
#include
#include
#include

using namespace std;
using ll=long long;
using P=pair;
const ll inf=1e18;
const int mod=1e9+7;

struct MobiusInversion{
	static constexpr int maxn=1e6+5;
	int cnt;
	vectorpri,vs,mu;
	vectorsm;
	MobiusInversion(int x=maxn):pri(x+5),vs(x+5),mu(x+5),sm(x+5){
		const int N=x-5;
		cnt=0;
		vs[0]=vs[1]=mu[1]=1;
		for(int i=2;i<=N;i++)
		{
			if(!vs[i])pri[++cnt]=i,mu[i]=-1;
			for(int j=1;j<=cnt&&i*pri[j]<=N;j++)
			{
				vs[i*pri[j]]=1;
				if(i%pri[j]==0)break;
				mu[i*pri[j]]=-mu[i];
			}
		}

		for(int i=1;i<=x;i++)
		{
			for(int j=i;j<=x;j+=i)
			{
				sm[j]+=mu[i]*j/i;
			}
		}
		for(int i=1;i<=x;i++)sm[i]+=sm[i-1];

	}

	ll getans(int n){
		ll ans=0;
		for(int l=1,r;l<=n;l=r+1)
		{
			r=n/(n/l);
			ans+=(n/l)*(sm[r]-sm[l-1]);
		}
		return ans%mod;
	};
    
}tt;

const int N=1e6+5;

void solve()
{
	ll n; cin>>n;
	cout<>t; 
	while(t--)solve();
	return 0;
}

数论分块例题

C/C++/C#相关栏目本月热门文章