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

wwt100127 · 2025-05-03 19:33:45 · 题解

思路

First

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

Second

设 f_i（只有 0 和 1 两种取值，或者说为一个 bool）表示第 i 个硬币是否需要翻转。

容易得到 f_i 的表达式：

因为是模 2 意义下的，所以容易得出 f*1 = \epsilon 。

两边同时卷 \mu，得到 f = \mu。

又因为是模 2 意义下的，所以 f_i 就可以表示为 \mu^2(i)。

所以 \text{Answer} = \sum_{i=1}^{n} \mu^2(i)。

Third

如果做的题足够多的话，容易得出 \mu^2(n) = \sum_{d^2 \mid n}\mu(d)（在 Proof 部分会给出证明）。

所以 \text{Answer} = \sum_{i=1}^{n} \sum_{d^2 \mid n} \mu(d)。

改变枚举顺序，则：

用杜教筛求 \mu 的前缀和，用数论分块求答案即可。

Proof

那么如何证明 \mu^2(n) = \sum_{d^2 \mid n}\mu(d) 呢？

不妨设 n = \prod_{i=1}^{k} p_i^{c_i}。

• 如果 \forall i \in \left[ 1,k \right ],c_i<2，则原等式显然成立（满足 d^2 \mid n 的 d 只有 1）。
• 否则，显然等式左边为 0。将所有 c_i < 2 的全部扔掉，并且令剩余的 c_i = c_i \mod 2。不妨设最后剩了 m 项，则 \mu(i) = 1 的个数共有 num_1 = \sum_{i=2k}C_{m}^{i}，\mu(i) = -1 的个数共有 num_2 = \sum_{i=2k+1} C_{m}^{i}。显然 num_1 = num_2，所以等式右边也是 0。

综上所述，原等式成立。

Code

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;
}