自动搬运

查看原文

来自洛谷，原作者为

	xht 好想爱这个世界啊

搬运于2025-08-24 22:10:45，当前版本为作者最后更新于2019-06-29 20:57:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意

求 $[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;
}