by hl666:

奇思妙想题

首先考虑如果区间内存在某个质数P，则对于两个数x,y，除非w(x)=w(LCM(x,y))（即x对应的质因子集合为y对应的质因子集合的子集），否则不如用w(x)+1的代价直接把x和P连起来

因此现在的做法就很显然了，先把所有质因子集合有包含关系的点连起来，最后把每个连通块和P

连起来即可

有一种比较好的处理方法是，对于某个数x，我们令g(x)为它的质因数集合中所有数的乘积（由于有去重，因此g(12)=2×3=6;g(27)=3）

此时x对应的质因子集合为y对应的质因子集合的子集等价于g(x)是g(y)的约数，那么直接在上面跑一个调和级数的枚举即可

令M=∑ri，总复杂度O(MlogM)

但如果区间内没有质数怎么办呢，不难发现这样的区间长度一定不会很长，我们可以直接暴力跑生成树

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<vector>

#include<utility>

#define RI register int

#define CI const int&

using namespace std;

typedef pair <int,int> pi;

const int N=1e6+5;

struct edge

{

int x,y,w;

inline edge(CI X=0,CI Y=0,CI W=0)

{

x=X; y=Y; w=W;

}

friend inline bool operator < (const edge& A,const edge& B)

{

return A.w<B.w;

}

}; int t,l,r,w[N],g[N],vis[N],sz[N],is_prime[N],fa[N];

inline void init(CI n)

{

RI i,j; for (i=1;i<=n;++i) g[i]=1;

for (i=2;i<=n;++i) if (!w[i])

{

is_prime[i]=1; g[i]=i; w[i]=1;

for (j=i*2;j<=n;j+=i) ++w[j],g[j]=g[j]*i;

}

}

inline int getfa(CI x)

{

return fa[x]!=x?fa[x]=getfa(fa[x]):x;

}

int main()

{

for (scanf("%d",&t),init(1e6);t;--t)

{

RI i,j; scanf("%d%d",&l,&r); int ans=0;

if (l==1)

{

for (i=2;i<=r;++i) ans+=w[i];

printf("%d\n",ans); continue;

}

bool has_prime=0;

for (i=l;i<=r;++i) if (is_prime[i]) has_prime=1;

if (has_prime)

{

for (i=1;i<=r;++i) sz[i]=vis[i]=0;

for (i=l;i<=r;++i) ++sz[g[i]];

for (i=2;i<=r;++i) if (!vis[i]&&sz[i])

{

ans+=w[i]*(sz[i]-1)+(w[i]+1); vis[i]=1;

for (j=i*2;j<=r;j+=i) if (!vis[j]&&sz[j])

vis[j]=1,ans+=w[j]*sz[j];

}

printf("%d\n",ans-2);

} else

{

vector <edge> E; for (i=l;i<=r;++i) fa[i]=i;

for (i=l;i<=r;++i) for (j=l;j<=r;++j)

E.push_back(edge(i,j,w[i]+w[j]-w[__gcd(i,j)]));

sort(E.begin(),E.end());

for (auto [x,y,w]:E)

{

if (getfa(x)==getfa(y)) continue;

ans+=w; fa[getfa(x)]=getfa(y);

}

printf("%d\n",ans);

}

}

return 0;

}