题解 P5438 【【XR-2】记忆】

· · 题解

题目大意

求 [l,r] 形成的排列中，相邻两个数的乘积是完全平方数的对数最多是多少。

前置知识

题解

将正整数 x 写成 x=k^{2}p 的形式（其中 k,p 为正整数），如果 k 最大，那么我们称 k^{2} 为 x 的最大平方因子。容易发现，p 的最大平方因子是 1。

易知两个数乘起来为完全平方数，当且仅当这两个数除去各自的最大平方因子后相等。

我们首先考虑 l=1 的情况。

考虑一个数 x，它的最大平方因子是 1。假设 x,2^{2}x,3^{2}x,...,k^{2}x \in [1,r]，那么我们只需要把这些数连续的放在一起，权值便会增加 k-1，因为每对相邻的数的乘积都是完全平方数。

因此，我们所求的答案等价于 [1,r] 中有多少个数最大平方因子不为 1。

再考虑 l≠1 的情况。

它与 l=1 的区别在于，原来考虑的 2^{2}x 到 k^{2}x 这 k-1 个数，每个数都能对权值有贡献，因为 x \in [l,r]。现在 x 可能不属于 [l,r] 了，那么每有一个这样的 x，权值就要减 1。

因此现在只需要计算 [1,l) 中有多少个最大平方因子为 1 的数 x 满足：存在一个数 c，使得 c^{2}x \in [l,r]。最后把答案减掉满足条件的 x 的数量就行了。

我们可以枚举 c，这样所有在 (\frac{l-1}{k^{2}},\frac{r}{k^{2}}] 的区间里的最大平方因子为 1 的数都是满足条件的 x。注意区间可能会重叠，实现的时候注意去重。

代码

#include<bits/stdc++.h>
#define N 10000010
#define ll long long
using namespace std;int crr;
int nop[N],p[N],mu[N],cnt,s[N],s2[N];
void mem(int n)
{
    mu[1]=1;for (int i=2;i<=n;i++)
    {
        if (!nop[i]) p[++cnt]=i,mu[i]=-1;
        for (int j=1;j<=cnt && i*p[j]<=n;j++)
        {
            nop[i*p[j]]=1;if (i%p[j]==0){mu[i*p[j]]=0;break;}mu[i*p[j]]=-mu[i];
        }
    }
    for (int i=1;i<=n;i++) s[i]=s[i-1]+mu[i],s2[i]=s2[i-1]+mu[i]*mu[i];
}
ll sol(ll x)
{
    if (x<=N-10) return x-s2[x];
    ll ans=0,p,m=sqrt(x),i;
    for (i=2;i<=m;i=p+1)
    {
        p=min((ll)(sqrt(x/(x/(i*i)))),m);
        ans-=x/(i*i)*(s[p]-s[i-1]);
    }
    return ans;
}
int main()
{
    mem(N-10);ll l,r,i,ans,lst=0;cin>>l>>r;
    ans=sol(r)-sol(l-1);lst=l-1;
    for (i=2;i*i<=r;i++)
    {
        ll p=(l-1)/(i*i),q=(r)/(i*i);q=min(q,lst);
        if (q>p) ans-=(q-p-sol(q)+sol(p));
        lst=p;
    }
    cout<<ans;
}