CF 2D求调

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
int t,n,a[200009];
ll ans;
struct bs{
	vector<ll> w;
	inline void clear(){
		w.clear(),w.resize((n+63)>>6);
		for(int i=0;i<w.size();++i) w[i]=0;
	}
	inline void set(int x){
		w[x>>6]|=(1ul<<(x&63));
	}
	inline bs l(int e){
		bs t;
		t.w.resize(w.size());
		for(int i=0;i<w.size();++i) t.w[i]=0;
		int o=(e>>6),r=(e&63);
		if(r){
    		t.w[0]=(w[0]<<r);
	    	for(int i=1;i<w.size();++i) t.w[i]=((w[i]<<r)|(w[i-1]>>(64-r)));
		}
		else{
		    for(int i=0;i<w.size();++i) t.w[i]=w[i];
		}
		if(o){
			for(int i=w.size()-1,j=w.size()-1-o;j>=0;--i,--j) t.w[i]=t.w[j];
			for(int i=o-1;i>=0;--i) t.w[i]=0;
		}
		if(n&63) t.w[w.size()-1]&=(1ul<<(n&63))-1;
		return t;
	}
	inline int p(const bs &o){
		int r=0;
		for(int i=0;i<w.size();++i) r+=__builtin_popcountll(w[i]&o.w[i]);
		return r;
	}
}f[449];
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>t;
	while(t--){
		cin>>n,ans=0;
		for(int i=1;i<=447;++i) f[i].clear();
		for(int i=0;i<n;++i) cin>>a[i],a[i]<=447&&(f[a[i]].set(i),0);
		for(int i=1;i<=447;++i){
			for(int j=i,k=1;j<n&&k<i;++k,j+=i) ans+=f[i].l(j).p(f[k])+f[k].l(j).p(f[i]);
			if(i*i<n) ans+=f[i].l(i*i).p(f[i]);
		}
		for(int i=0;i<n;++i) if(a[i]>=448) for(int j=i%a[i];j<n;j+=a[i]) if(a[j]<=447&&a[i]*(ll)a[j]==abs(j-i)) ++ans;
		cout<<ans<<"\n";
	}
	return 0;
}