返回首页 返回专题

【BZOJ4816】神犇和蒟蒻 题解

第一问

嗯我们理性思考一下

μ的定义：若某数x含有两个相同质因子，则μ(x)=0

然后，这题要你求μ(x²)，嗯，平方，平方，平方……我去你丫的不都是0吗！

所以除了μ(1²)=1之外，其它的就都是0了，所以答案就是1

鉴定完毕，这是一个假问

第二问

来画一个柿子

ps. 倒数第二个柿子的phi(j)前面漏了一个j……

然后就可以愉快地杜教筛了！

发现第一项分子乘起来好像会爆long long，然而边乘边模肯定不行，因为还有除，所以可以先算出6在模1000000007意义下的逆元是166666668，这样就可以边乘边模了

千万不要忽略后面那一项的i，这个在整除分块算的时候，用一个等差数列求和公式就出来了

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

typedef long long LL;
const int N=7000000;
int prime[664579+10],tot=0;
LL phi[N+10];
bool mark[N+10];
map<int,LL> sphi;

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

LL Sum(LL n)
{
	if(n<=N) return phi[n]%Mod;
	if(sphi.count(n)) return sphi[n];
	LL div,res=(n*(n+1)%Mod)*(2*n+1)%Mod;
	res=res*inv6%Mod;
	for(LL i=2;i<=n;i=div+1)
	{
		div=n/(n/i);
		LL s=((i+div)*(div-i+1)%Mod)*inv2%Mod;
		res=(res-s*Sum(n/i)%Mod+Mod)%Mod;
	}
	sphi[n]=res;
	return res;
}

int main()
{
	Init();
	LL n;
	cin>>n;
	puts("1");
	cout<<Sum(n)<<endl;
	return 0;
}