【洛谷P5438】【XR-2】记忆
数论
题目大意：
给定 $l\sim r$ 的所有整数，要求将其排成一列，使得相邻两个数乘积是完全平方数的对数最多，求最多的对数。
题解：
令 $f(n)=\max\limits_{x^2|n}x$。则一个数 $x$ 可以表示为 $f(x)^2p$，不难得出 $f(p)=1$。
两个数能产生贡献，当且仅当两个数的表示中 $p$ 相等。
考虑 $l=1$ 的情况，我们对每个 $f(x)=1$ 的 $x$，将 $x,2^2x,3^3x,\dots,k^2x$ 放在一起，即可产生 $k-1$ 的贡献。这样显然是最多的。
我们求出 $[l,r]$ 中 $f(x)\neq 1$ 的数的个数，即为答案。
考虑 $l > 1$ 的情况。我们发现，刚才计算贡献的时候，没产生贡献的数就是那些 $f(x)=1$ 的数。而上面计算的时候，我们相当于是对每个 $x$ 在计算贡献。这个多出的 $1$ 的贡献本应该在 $x$ 那个数本身处减去的，由于当前的区间为 $[l,r]$，所以这个 $x$ 产生的贡献多算了 $1$。
我们先求出 $[l,r]$ 中 $f(x)\neq 1$ 的数的个数，然后考虑减掉 $[1,l-1]$ 中 $f(x)=1$ 中的数的贡献。
如果一个数 $x\in[1,l-1]$ 并且 $f(x)=1$，且存在 $c>1$ 满足 $c^2x\in[l,r]$，那么这个数计算贡献时就多算了 $1$。我们需要统计这样的数的个数。
我们考虑枚举 $c$，那么相当于求 $[\lceil\frac{l-1}{c^2}\rceil,\lfloor\frac{r}{c^2}\rfloor]$ 中 $f(x)=1$ 的数 $x$ 的个数。这里的区间有可能重复，在计算的时候需要注意。
那么现在的问题是，如何求 $\sum\limits_{i=1}^n[f(i)=1]$。
推式子：
于是我们可以在 $O(\sqrt n)$ 的时间内求出 $n$ 以内 $f(x)=1$ 的 $x$ 的个数。
那么我们枚举 $c$，每次需要花 $O(\frac{\sqrt n}{c})$ 的时间。
总时间复杂度 $O(\sqrt n\times(1+\frac 1 2+\frac 1 3+\frac 1{4}+\dots))=O(\sqrt n\log n)$。
在求值的时候需要再用整除分块进一步优化。
单次复杂度证明：
当 $d\leq \sqrt[3]n$ 时，只有 $O(\sqrt[3]n)$ 个不同的 $d$。
当 $d>\sqrt[3]n$ 时，只有 $O(\sqrt[3]n)$ 个不同的 $\lfloor\frac{n}{d^2}\rfloor$。
故单次复杂度为 $O(\sqrt[3]n)$。
令 $g(n)=\sum\limits_{k=1}^n \frac{1}{\sqrt[3]{k^2}}$.
那么总时间复杂度为 $O(\sqrt n+\sqrt[3]n \times g(\sqrt n))$，当 $n\leq 10^{14}$ 时可以认为是 $O(\sqrt n)$。
需要线性筛处理 $\mu$ 函数，及其前缀和、平方前缀和（优化常数）等信息。
Code：
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
LL l,r;
bool vis[10000001];int mu[10000001],pri[10000001/15],tot,pre[10000001],M,pr[10000001];
void sieve(const int n){
mu[1]=1;
for(register int i=2;i<=n;++i){
if(!vis[i])pri[++tot]=i,mu[i]=-1;
for(int j=1;j<=tot&&i*pri[j]<=n;++j){
vis[i*pri[j]]=1;
if(i%pri[j]==0)
break;
else
mu[i*pri[j]]=-mu[i];
}
}
for(register int i=1;i<=n;++i)pre[i]=pre[i-1]+mu[i]*mu[i],pr[i]=pr[i-1]+mu[i];
}
inline LL solve(LL n){
if(n<M)return pre[n];
int s=sqrt(n)+1e-9;
LL ans=0;
for(register int l=1,r;l<=s;l=r+1){
r=sqrt(n/(n/l/l));
ans+=(n/l/l)*(pr[r]-pr[l-1]);
}
return ans;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>l>>r;
sieve(M=sqrt(r));
LL ans=r-solve(r)-l+1+solve(l-1),lst=l;
for(int i=2;i<=M;++i){
LL L=(l-1)/i/i+1,R=min(r/i/i,lst-1);
if(L>R)continue;
ans-=solve(R)-solve(L-1);
lst=L;
}
cout<<ans<<endl;
return 0;
}