[BZOJ4916]神犇(Monster_Qi)和蒟蒻(SWHsz)

很久很久以前，有一只神犇叫Monster_Qi;

很久很久之后，有一只蒟蒻叫SWHsz;

1<=N<=1E9,A、B模1E9+7;

求这个。

求μ的话直接输出1就行了因为除了1的平方外都有平方因子。

求φ的话就有个显而易见的结论就是$φ(n^2)=φ(n)n$,列出φ的一般式就行了。

然后就是套杜教筛的模板了。

要凑 $f \cdot g=h$

$ h(i)=\sum _{d|i} φ(d)dg(i/d) $
显而易见的，g是$id$函数，$h(i)=i^2$

然后随便搞了。

#include <iostream>

#include <cstdio>

#include <map>

using namespace std;

map<long long,long long>mp;

long long n;

const int N = 10000005,NI2=500000004,NI6=166666668,mod=1e9+7;

long long ph[N],prime[N],cnt;

bool vis[N];

void phhh() {

    ph[1]=1;

    for(int i=2; i<=N-5; i++) {

        if(!vis[i]) prime[++cnt]=i,ph[i]=i-1;

        for(int j=1; j<=cnt; j++) {

            if(i*prime[j]<=N-5) vis[i*prime[j]]=1;else break;

            if(i%prime[j]==0){ph[i*prime[j]]=ph[i]*prime[j];break;}

            else ph[i*prime[j]]=ph[i]*ph[prime[j]];

        }

    }

    for(int i=1;i<=N-5;i++) ph[i]=(ph[i]*i+ph[i-1])%mod;

}

long long solve(long long x) {

	if(N-5>=x) return ph[x];

	if(mp.count(x)) return mp[x];

	long long ans=x*((x+1)%mod)%mod*((2*x%mod+1)%mod)%mod*NI6%mod;

	for(long long i=2,nxti;i<=x;i=nxti+1) {

		nxti=x/(x/i);

		ans=(ans-(nxti+i)%mod*(nxti-i+1ll)%mod*NI2%mod*solve(x/i))%mod;

	}

	return mp[x]=(ans+mod)%mod;

}

int main() {

	phhh();

	scanf("%lld",&n);

	printf("1\n%lld",solve(n));

}

巴特西

[BZOJ4916]神犇(Monster_Qi)和蒟蒻(SWHsz)

最新文章

热门文章