自动搬运

查看原文

来自洛谷，原作者为

	Otomachi_Una_ We will never forget those days, thanks for everything.

搬运于2025-08-24 22:54:19，当前版本为作者最后更新于2024-02-12 14:37:29，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

我自信满满的看完题目，然后糊了一个做法：

把每个 $a_i$ 分解质因数，每个质数赋一个随机权值。$S_i$ 维护一下前缀乘积质因子的异或，用 map 统计一下就行了。

然后你惊奇的发现 $a_i\leq 10^{36}$，即使用 Pollard Rho 也有 $\mathcal O(a_i^{0.25})$ 的复杂度，也就是一个数也分解不出来。

尝试考虑一些比较玄学的做法。大平方数 $N$ 有一个很好的性质，就是对任意奇质数 $p$，$N\bmod p$ 总是 $\bmod p$ 的二次剩余。

根据众所周知的知识，二次剩余性质非常好，比如：

• 奇质数 $p$ 恰有 $\dfrac{p-1}{2}$ 的非零二次剩余（刚好一半）。
• 一个数 $x$ 是 $\bmod p$ 意义下的二次剩余当且仅当 $x^{\frac{p-1}{2}}\equiv 1\pmod p$，否则就是 $-1$。
• 二次剩余乘上二次剩余还是二次剩余；非二次剩余乘上非二次剩余是二次剩余；二次剩余乘上非二次剩余还是非二次剩余。（这些结论可以从上面结论 $2$ 推出来）。

这启示我们一个玄学的做法：

随机选 $T=60$ 个大质数，保证每个质数 $P$ 都和所有 $a_i$ 互质。 然后算二次剩余。把非二次剩余的位记为 $1$，那么一个连续段是合法的当且仅当这一段所有数异或为 $0$。

这样子复杂度是 $\mathcal O(nT\log p)$ 的，考虑去消掉这个 $\log p$。

这里的 $\log p$ 是在判断二次剩余，我们可以考虑找一些小的 $p$ 然后 $\mathcal O(p)$ 提前预处理出来二次剩余（因为这样子排除二次剩余的概率是一样的），但是这样子就不能保证 $P$ 和所有 $a_i$ 互质。

考虑处理掉 $P|a_i$ 的情况，我们可以舍弃掉 $a_i$ 的所有 $P$ 因子。因为这样子我们放弃 $P$ 因子的判断转而判断其他因子正确性不会影响。

复杂度是 $\mathcal O((n+P)T)$。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define LL __int128
#define MP make_pair
const int MAXN=3e5+5;
const int inf=1e7;
mt19937 rnd(time(0));
int n;LL a[MAXN];ll b[MAXN];
bool is[inf];
unordered_map<ll,vector<int> > mp;
LL read(){
	LL r=0;char c=getchar();
	while(c<'0'||c>'9') c=getchar();
	while(c>='0'&&c<='9') r=10*r+c-'0',c=getchar();
	return r;
}
ll ksm(ll a,int b,const int MOD){ll r=1;while(b){if(b&1)r=r*a%MOD;a=a*a%MOD,b>>=1;}return r;}
bool is_prime(int x){
	for(int i=2;i*i<=x;i++) if(x%i==0) return false;
	return true;
}
bool occ(ll x){
	for(int i=1;i<=n;i++) if(a[i]%x==0) return true;
	return false;
}
int main(){
	// freopen("ex_5.in","r",stdin);
	// freopen("square.out","w",stdout);
	n=read();
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=0;i<60;i++){
		int p=rnd()%inf+1;
		while(!is_prime(p)) p=rnd()%inf+1;
		cerr<<p<<endl;
		memset(is,0,sizeof(is));
		for(ll i=1;i<p;i++) is[i*i%p]=true;
		for(int j=1;j<=n;j++){
			LL x=a[j];
			while(x%p==0) x/=p;
			if(!is[x%p]) b[j]|=(1ll<<i);
		}
	}
	for(int i=1;i<=n;i++) b[i]^=b[i-1];
	ll ans=0;
	for(int i=0;i<=n;i++) ans+=mp[b[i]].size(),mp[b[i]].push_back(i);
	cout<<ans<<'\n';
	ans=0;
	for(int i=0;i<=n&&ans<1e5;i++){
		for(int j:mp[b[i]]) if(j>i&&ans<1e5){
			ans++;
			cout<<i+1<<' '<<j<<'\n';
		}
	}
	return 0;
}