专栏文章

题解：AT_xmascon19_d Sum of (-1)^f(n)

llittlez_meow
AT_xmascon19_d题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqimwak
此快照首次捕获于
2025/12/04 05:25
3 个月前
此快照最后确认于
2025/12/04 05:25
3 个月前
查看原文
PN 筛竟然是这么小众的筛法吗？

思路

显然 f(x)f(x) 是完全和性函数，故 (−1)f(x)(-1)^{f(x)} 是（完全）积性函数。下面设 F(x)=(−1)f(x)F(x)=(-1)^{f(x)}。
可以直接 min_25，但是我不会。又懒得去推这个函数如何杜教筛。
所以考虑一些科技飞升做法，比如 PN 筛。下面会给出 PN 筛的流程，但不会有定义和证明。
首先寻找质数 pp 处取值相同的积性函数 GG。我们有 (−1)f(p)=−1=μ(p)(-1)^{f(p)}=-1=\mu(p)，所以取 G(x)=μ(x)G(x)=\mu(x)。如无特殊说明，下面 pp 均为质数。
然后设积性函数 H(x)H(x) 满足 F=G∗HF=G*H，这里 ∗* 是狄利克雷卷积，则 HH 只在 PN 处不为 00。
则我们有 F(pk)=∑i=0kμ(pi)H(pk−i)F(p^k)=\sum\limits_{i=0}^k \mu(p^i)H(p^{k-i})。简单化简得到 (−1)k=H(pk)−H(pk−1)(-1)^k=H(p^k)-H(p^{k-1})。结合 H(p)=0H(p)=0，有 H(pk)=[2∣k]H(p^k)=[2|k]。
我们有 ∑i=1nF(i)=∑i=1n∑d∣iH(d)μ(id)\sum\limits_{i=1}^n F(i)=\sum\limits_{i=1}^n\sum\limits_{d|i}H(d)\mu(\dfrac{i}{d})。
枚举因数变枚举倍数得到 ∑i=1nF(i)=∑d=1n∑i=1⌊nd⌋μ(i)H(d)\sum\limits_{i=1}^n F(i)=\sum\limits_{d=1}^n\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\mu(i)H(d)。
设 S(x)=∑i=1xμ(i)S(x)=\sum\limits_{i=1}^x\mu(i)，化简得到 ∑i=1nF(i)=∑d=1nH(d)S(⌊nd⌋)\sum\limits_{i=1}^n F(i)=\sum\limits_{d=1}^n H(d)S(\lfloor\dfrac{n}{d}\rfloor)。
枚举令 H(d)≠0H(d)\neq 0 的 O(n)O(\sqrt n) 个 PN，用一次杜教筛算出 O(n)O(\sqrt n) 个本质不同的 S(⌊nd⌋)S(\lfloor\dfrac{n}{d}\rfloor) 即可。
瓶颈在于一次杜教筛，时间复杂度 O(n23)O(n^{\frac 2 3})。

代码

CPP
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#define F(i,a,b) for(int i(a),i##i##end(b);i<=i##i##end;++i)
#define R(i,a,b) for(int i(a),i##i##end(b);i>=i##i##end;--i)
#define ll long long
#define File(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)
using namespace std;
const int MAXN=5e7+1,LIM=1e6+1;
bool vis[MAXN];
ll mu[MAXN];
int pr[3001135],cnt;
inline void init(){
	mu[1]=1;
	F(i,2,MAXN-1){
		if(!vis[i]) pr[++cnt]=i,mu[i]=-1;
		F(j,1,cnt){
			ll k=i*pr[j];
			if(k>=MAXN) break;
			vis[k]=1;
			if(i%pr[j]) mu[k]=-mu[i];
			else break;
		}
	}
	F(i,2,MAXN-1) mu[i]+=mu[i-1];
	return;
}
__gnu_pbds::gp_hash_table<ll,int>res;
ll n,ans;
ll S(ll x){
	if(x<MAXN&&x!=n) return mu[x];
	if(res.find(x)!=res.end()) return res[x];
	ll ans=1;
	for(ll l=2,r;l<=x;l=r+1){
		ll qwq=x/l;
		r=x/qwq;
		ans=ans-(r-l+1)*S(qwq);
	}
	return res[x]=ans;
}
void dfs(int step,ll now,ll H){
	ll pri=pr[step],nxt=pri*pri;
	if(step>cnt||now>n/nxt){
		ans+=H*S(n/now);
		return;
	}
	dfs(step+1,now,H);
	for(int expo(2);now*nxt<=n;++expo,nxt*=pri) dfs(step+1,now*nxt,H*((expo&1)==0));
	return;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	init(),S(n);
	dfs(1,1,1);
	cout<<ans;
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...