我自信满满的看完题目，然后......

· · 题解

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

把每个 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 的二次剩余。

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

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

随机选 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;
}