返回首页 返回专题

【BZOJ4176】Lucas的数论 题解

SDOI2015约数个数和那道题，给我们提供了一个非常好的思路

这题的N=M，最后的柿子稍微小了一些：Σ{μ(k)f²(n/k)}(k=1~n)，其中f(n)=Σ{n/i}(i=1~n)

那么我们可以对整个柿子整除分块，μ(k)可以用杜教筛求，方法见【BZOJ3944】Sum 题解，f则可以再套一层整除分块来求

最后的复杂度我也不会分析了，反正能A

#include<bits/stdc++.h>
#define Mod 1000000007
using namespace std;

typedef long long LL;
const int N=7000000;
int u[N+10];
int prime[650000],tot=0;
bool mark[N+10];
map<int,int> mu;

void Init()
{
	u[1]=1;
	for(int i=2;i<=N;i++)
	{
		if(!mark[i]) prime[++tot]=i,u[i]=-1;
		for(int j=1;j<=tot&&i*prime[j]<=N;j++)
		{
			mark[i*prime[j]]=1;
			if(i%prime[j]) u[i*prime[j]]=-u[i];
			else u[i*prime[j]]=0;
		}
	}
	for(int i=2;i<=N;i++) u[i]+=u[i-1];
}

int Su(int n)
{
	if(n<=N) return u[n];
	if(mu.count(n)) return mu[n];
	int div,res=1;
	for(int i=2;i<=n;i=div+1)
	{
		div=n/(n/i);
		res-=(div-i+1)*Su(n/i);
	}
	mu[n]=res;
	return res;
}

int Sdiv(int n)
{
	int div;LL ans=0;
	for(int i=1;i<=n;i=div+1)
	{
		div=n/(n/i);
		ans=(ans+(div-i+1)*(n/i)%Mod)%Mod;
	}
	return ans;
}

int main()
{
	Init();
	int n,div;cin>>n;
	LL ans=0;
	for(int i=1;i<=n;i=div+1)
	{
		div=n/(n/i);
		int smu=Su(div)-Su(i-1);
		LL sf=Sdiv(n/i);
		sf=sf*sf%Mod;
		ans=(ans+(LL)smu*sf%Mod+Mod)%Mod;
	}
	cout<<ans<<endl;
	return 0;
}