【2025.2 省选模拟赛 3】次方数 做题记录

给定一个长 $n$ 的序列 $a$ 和一个正整数 $k$，求有多少个无序区间对 $([l_1,r_1],[l_2,r_2])$ 满足 $l_1\le r_1<l_2\le r_2$ 且 $\left(\prod\limits_{l_1\le i\le r_1}a_i\right)\times \left(\prod\limits_{l_1\le i\le r_1}a_i\right)$ 是 $k$ 次方数，即存在某个正整数 $x$ 使得其等于 $x^k$。

$1\le n\le 500$，$1\le a_i\le 10^{36}$，$1\le k\le 10^9$。

首先一个数是 $k$ 次方数当且仅当它每个质因子的指数都是 $k$ 的倍数，故若可以质因数分解就能简单做了。

具体的，可以使用哈希判断两个数的乘积是否 $k$ 次方数：设共有 $m$ 个质因子，$x$ 每个质因子的指数为 $x_{[1,m]}$，$y$ 的则为 $y_{[1,m]}$，则 $xy$ 是 $k$ 次方数当且仅当 $\forall i$，都有 $x_i\equiv y_i\pmod m$。

那么从左往右扫描线，扫到 $i$ 的时候将 $j\in [i,n]$ 的所有区间 $[i,j]$ 拿出来算一下哈希值，查询对应哈希值在桶中有多少个；再将 $j\in [1,i]$ 的所有区间 $[j,i]$ 拿出来算哈希值放进桶里。

现在的问题是值域太大了，任何质因数分解算法都不可用。

根据强大的注意力，我们似乎并不需要将每个数都分解成素数的乘积。具体的，若可以找到一个“伪素数”集合 $st$，使得：

• $\forall x,y\in st,x\not=y$ 都有 $\gcd(x,y)=1$；
• $\forall x\in st$，不存在某个 $k>1$ 使得 $x$ 是 $k$ 次方数；
• $\forall i$，$a_i$ 可以被唯一分解成 $st$ 中数的乘积；

不难发现将这些“伪素数”当作素数来做之前的算法就是正确的。

求解伪素数则考虑增量法，设当前伪素数集合为 $st$，要插入一个数 $x$，则：

• 先 $\forall y\in st$，将 $x$ 不断除掉 $y$ 直到 $y$ 不再是 $x$ 的因子；
• 这时还不能直接将 $x$ 插入 $st$ 中，因为可能存在某个 $y\in st$ 满足 $\gcd(x,y)\not=1$。扫一遍找到某个这样的 $y$，设 $\gcd(x,y)=g$：
  • 将 $g$ 插入 $st$；
  • 将 $y$ 从 $st$ 中删去，然后将其不断除掉 $g$，设最终变为了 $y'$，则递归插入 $y'$；
  • 将 $x$ 不断除掉 $g$；
• 不断找到这样的 $y$ 直到不存在，然后若 $x$ 非 $1$ 则插入 $st$；

不难发现这样的过程一定能结束，因为 $|st|$ 有个上限是 $n\log V$（$V$ 为值域），每一轮额外增加一个数，故时间复杂度上限为 $O(n^2\log V)$。

最后需要将 $st$ 中的数开根使得其满足第二条性质。

时间复杂度大概 $O(n^3\log V)$，代码如下：

#include <iostream>
#include <cstdio>
#include <set>
#include <vector>
#include <map>
#include <random>

using namespace std;

using LL=__uint128_t;
using ll=long long;
using ull=unsigned long long;

template<typename T>
inline void read(T &x)
{
	char c=getchar();
	T w=1;
	x=0;
	while(c<'0'||c>'9') w=(c=='-'?-w:w),c=getchar();
	while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
	x*=w;
}

template<typename T>
void writen(T x)
{
	if(x<0) return putchar('-'),writen(-x),void();
	if(x>9) writen(x/10);
	putchar(x%10+'0');
}

const int S=505;

mt19937_64 rnd;
int n,m;
LL a[S];
set<LL> st;
vector<pair<LL,ull> > vec;
map<ull,int> mp;

inline LL gcd(LL x,LL y)
{
	LL t=x%y;
	while(t!=0) x=y,y=t,t=x%y;
	return y;
}

inline LL qpow(LL x,int y,LL lim)
{
	LL res=1;
	while(y>0)
	{
		if(res>lim/x) return -1;
		if(y&1) res*=x;
		y>>=1;
		if(y==0) break;
		if(x>lim/x) return -1;
		x*=x;
	}
	return res;
}

inline LL sqrt(LL x,int k)
{
	LL lb=1,rb=x,res=1;
	while(lb<=rb)
	{
		LL mid=lb+rb>>1;
		if(qpow(mid,k,x)!=-1) res=mid,lb=mid+1;
		else rb=mid-1;
	}
	return res;
}

void ins(LL a)
{
	if(a==1) return;
	for(LL x:st) while(a%x==0) a/=x;
	while(1)
	{
		bool fl=false;
		for(LL x:st)
		{
			LL g=gcd(x,a);
			if(g!=1)
			{
				st.erase(x);
				while(x%g==0) x/=g;
				st.insert(g);
				ins(x);
				while(a%g==0) a/=g;
				fl=true;
				break;
			}
		}
		if(!fl)
		{
			if(a!=1) st.insert(a);
			break;
		}
	}
}

int main()
{
	read(n),read(m);
	for(int i=1;i<=n;i++) read(a[i]);
	for(int i=1;i<=n;i++) ins(a[i]);
	for(LL x:st)
	{
		LL res=x;
		for(int i=2;i<=128;i++)
		{
			LL pre=sqrt(x,i);
			if(qpow(pre,i,x)==x) res=pre;
		}
		vec.emplace_back(res,rnd());
	}
	ll ans=0;
	for(int i=1;i<=n;i++)
	{
		int sz=vec.size();
		vector<int> ct(sz,0);
		for(int j=i;j<=n;j++)
		{
			LL x=a[j];
			for(int k=0;k<sz;k++)
				while(x%vec[k].first==0) x/=vec[k].first,ct[k]++;
			ull pre=0;
			for(int k=0;k<sz;k++)
				pre+=vec[k].second*((m-ct[k]%m)%m);
			ans+=mp[pre];
		}
		for(int k=0;k<sz;k++) ct[k]=0;
		for(int j=i;j>=1;j--)
		{
			LL x=a[j];
			for(int k=0;k<sz;k++)
				while(x%vec[k].first==0) x/=vec[k].first,ct[k]++;
			ull pre=0;
			for(int k=0;k<sz;k++)
				pre+=vec[k].second*(ct[k]%m);
			mp[pre]++;
		}
	}
	printf("%lld\n",ans);
	return 0;
}