（题目传送门）
受益良多啊……
设 \(f(i)\) 表示第 \(i\) 枚硬币是否需要被翻转，以下所有运算均在模 \(2\) 意义下进行。
初始化 \(f(1)=1\)，递推式有 \(f(i)=\sum\limits_{d\mid i,d\ne i}f(d)\)，答案即求 \(\sum\limits_{i=1}^nf(i)\)。
观察发现 \(\sum\limits_{d\mid i}f(d)=2f(i)=[i=1]\)，写成卷积形式就是 \(f*I=\epsilon\)，反演一下得 \(f=\mu\)。
当 \(\mu(i)=-1\) 时，可令 \(f(i)\leftarrow 1\)，因此答案即求 \(\sum\limits_{i=1}^n\mu^2(i)\)。
来到本题一个重要的 Trick —— \(\mu^2\) 的前缀和计算。
考虑 \(\mu^2(i)\) 的实际意义，即 \(i\) 是否含有平方因子。那么将 \(i\) 质因数分解得 \(\prod p_i^{c_i}\)，令 \(P=\prod p_i^{\lfloor c_i/2\rfloor}\)，那么 \(\mu^2(i)=1 \Leftrightarrow P=1\)。因此有 \(\mu^2(i)=[P=1]=\sum\limits_{d\mid P}\mu(d)=\sum\limits_{d^2\mid i}\mu(d)\)。
所以
\[\sum\limits_{i=1}^n\mu^2(i)=\sum\limits_{i=1}^{\sqrt{n}}\mu(i)\left\lfloor\dfrac{n}{i^2}\right\rfloor \]那么问题就涉及到了高次整除分块。对 \(\left\lfloor\dfrac{n}{i^2}\right\rfloor\) 整除分块，\(r=\sqrt{\left\lfloor\dfrac{n}{\left\lfloor\dfrac{n}{i^2}\right\rfloor}\right\rfloor}\)，时间复杂度 \(\mathcal{O}(n^{\frac{1}{3}})\)。
预处理 \(\mathcal{O}(n^{\frac{2}{5}})\) 的前缀和可以做到复杂度 \(\mathcal{O}(n^\frac{2}{5})\)，证明太难不会。
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1.6e7+10;
LL n,lim,ans;
int v[N],prime[N],mu[N],sum[N],tot;
unordered_map <LL,LL> tmp;
void prework()
{
mu[1]=1;
for(int i=2; i<=lim; i++)
{
if(!v[i])
{
v[i]=i;
prime[++tot]=i;
mu[i]=-1;
}
for(int j=1; j<=tot; j++)
{
if(prime[j]>v[i] || prime[j]>lim/i)
break;
v[i*prime[j]]=prime[j];
if(i%prime[j]==0)
break;
mu[i*prime[j]]=-mu[i];
}
}
for(int i=1; i<=lim; i++)
sum[i]=sum[i-1]+mu[i];
}
LL query(LL n)
{
if(n<=lim)
return (LL)sum[n];
auto it=tmp.find(n);
if(it!=tmp.end())
return it->second;
LL res=1;
for(LL l=2,r; l<=n; l=r+1)
{
r=n/(n/l);
res-=(r-l+1)*query(n/l);
}
return tmp[n]=res;
}
signed main()
{
scanf("%lld",&n);
lim=powl(n,2.0/5)+10;
prework();
for(LL l=1,r; l<=sqrtl(n); l=r+1)
{
r=sqrtl(n/(n/(l*l)));
ans+=(query(r)-query(l-1))*(n/(l*l));
}
printf("%lld\n",ans);
return 0;
}