求hack这个结论：左端点相同，且右端点位置两数组的后缀gcd分别相同，则结果相同

利用这个结论写的代码，但是WA on test 2

#include <bits/stdc++.h>
using namespace std;
const int N=200007;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int gcd(int a,int b,int c){return gcd(a,gcd(b,c));}
int lg[N],l[53],r[53],cnt,n;
struct st{
	int val[19][N];
	int& operator[](int x){return val[0][x];}
	void build(int n){for(int i=1;(1<<i)<=n;i++) for(int j=1;j+(1<<i)-1<=n;j++) val[i][j]=gcd(val[i-1][j],val[i-1][j+(1<<(i-1))]);}
	int query(int l,int r){
		if(l>r) return 0;
		int x=lg[r-l+1];
		return gcd(val[x][l],val[x][r-(1<<x)+1]);
	}
} a,b;
struct node{
	int val,cnt;
	node operator+(node o){
		if(val>o.val) return *this;
		if(val<o.val) return o;
		return {val,cnt+o.cnt};
	}
} ans;
ostream& operator<<(ostream& out,node a){return out<<a.val<<' '<<a.cnt<<'\n';}
int f(int l,int r){return gcd(a.query(1,l-1),b.query(l,r),a.query(r+1,n))+gcd(b.query(1,l-1),a.query(l,r),b.query(r+1,n));}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t;
	cin>>t;
	lg[0]=-1;
	for(int i=1;i<N;i++) lg[i]=lg[i/2]+1;
	while(t-->0){
		cin>>n;
		for(int i=1;i<=n;i++) cin>>a[i];
		for(int i=1;i<=n;i++) cin>>b[i];
		ans={0,0};
		a.build(n),b.build(n);
		cnt=0;
		l[++cnt]=n+1,r[cnt]=n+1;
		int ga=a[n],gb=b[n],tmp=n;
		for(int i=n-1;i;i--) if((a[i]%ga)||(b[i]%gb)) l[++cnt]=i+1,r[cnt]=tmp,tmp=i,ga=gcd(ga,a[i]),gb=gcd(gb,b[i]);
		l[++cnt]=1,r[cnt]=tmp;
		for(int i=1;i<=n;i++) {
			int j=1;
			while(l[j]>i) ans=ans+node{f(i,r[j]-1),r[j]-l[j]+1},j++;
			if(r[j]>i)ans=ans+node{f(i,r[j]-1),r[j]-i};
		}
		cout<<ans;
	}
}