专栏文章

题解：P9238 [蓝桥杯 2023 省 A] 翻转硬币

wwwt100127
P9238题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@mipfcl9z
此快照首次捕获于
2025/12/03 11:05
3 个月前
此快照最后确认于
2025/12/03 11:05
3 个月前
查看原文

思路

First

很容易得到一个 O(nlog⁡n)O(n \log n) 的做法。从 11 到 nn 枚举每个点 ii，如果硬币朝下，则将 ii 的倍数全部翻转。

Second

设 fif_i（只有 00 和 11 两种取值，或者说为一个 bool）表示第 ii 个硬币是否需要翻转。
容易得到 fif_i 的表达式：
fi={1 if i=1∑d∣i,d≠ifd otherwise f_i = \begin{cases} 1 & \text{ if } i=1 \\ \sum_{d \mid i,d \ne i} f_d & \text{ otherwise } \end{cases}
因为是模 22 意义下的，所以容易得出 f∗1=ϵf*1 = \epsilon 。
两边同时卷 μ\mu，得到 f=μf = \mu。
又因为是模 22 意义下的，所以 fif_i 就可以表示为 μ2(i)\mu^2(i)。
所以 Answer=∑i=1nμ2(i)\text{Answer} = \sum_{i=1}^{n} \mu^2(i)。

Third

如果做的题足够多的话，容易得出 μ2(n)=∑d2∣nμ(d)\mu^2(n) = \sum_{d^2 \mid n}\mu(d)（在 Proof 部分会给出证明）。
所以 Answer=∑i=1n∑d2∣nμ(d)\text{Answer} = \sum_{i=1}^{n} \sum_{d^2 \mid n} \mu(d)。
改变枚举顺序，则：
Answer=∑d=1n⌊nd2⌋μ(d)\text{Answer} = \sum_{d=1}^{\sqrt{n}} \left \lfloor \frac{n}{d^2} \right \rfloor \mu(d)
用杜教筛求 μ\mu 的前缀和，用数论分块求答案即可。

Proof

那么如何证明 μ2(n)=∑d2∣nμ(d)\mu^2(n) = \sum_{d^2 \mid n}\mu(d) 呢？
不妨设 n=∏i=1kpicin = \prod_{i=1}^{k} p_i^{c_i}。
  • 如果 ∀i∈[1,k],ci<2\forall i \in \left[ 1,k \right ],c_i<2，则原等式显然成立（满足 d2∣nd^2 \mid n 的 dd 只有 11）。
  • 否则，显然等式左边为 00。将所有 ci<2c_i < 2 的全部扔掉，并且令剩余的 ci=cimod  2c_i = c_i \mod 2。不妨设最后剩了 mm 项，则 μ(i)=1\mu(i) = 1 的个数共有 num1=∑i=2kCminum_1 = \sum_{i=2k}C_{m}^{i}，μ(i)=−1\mu(i) = -1 的个数共有 num2=∑i=2k+1Cminum_2 = \sum_{i=2k+1} C_{m}^{i}。显然 num1=num2num_1 = num_2，所以等式右边也是 00。
综上所述，原等式成立。

Code

CPP
const int N=2e7+5;
int n,Prime[N],cnt,Mu[N];
bool vis[N];
map<int,int> Map;
void init(int n)
{
	int i,j; Mu[1]=1;
	for(i=2;i<=n;i++)
	{
		if(!vis[i]) Prime[++cnt]=i,Mu[i]=-1;
		for(j=1;j<=cnt && i*Prime[j]<=n;j++)
		{
			vis[i*Prime[j]]=1;
			if(i%Prime[j]==0)
			{
				Mu[i*Prime[j]]=0;
				break;
			}
			Mu[i*Prime[j]]=-Mu[i];
		}
	}
	for(i=1;i<=n;i++) Mu[i]+=Mu[i-1];
}
int Mu_SUM(int n)
{
	if(n<=2e7) return Mu[n];
	if(Map[n]) return Map[n];
	int L,R,ans=1;
	for(L=2;L<=n;L=R+1)
	{
		R=n/(n/L);
		ans-=(R-L+1)*Mu_SUM(n/L);
	}
	return Map[n]=ans;
}
int Love_Forever()
{
	int L,R,ans=0;
	n=read(); init(2e7);
	for(L=1;L*L<=n;L=R+1)
	{
		R=sqrt(n/(n/L/L));
		ans+=(n/L/L)*(Mu_SUM(R)-Mu_SUM(L-1));
	}
	return ans;
}

评论

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

正在加载评论...