Codeforces Round 972 (Div. 2) D. Alter the GCD（二分+gcd性质）

题目

每次给定n(n<=2e5)和两个长为n的数组a，b(1<=ai,bi<=1e9)

需要进行以下操作恰好一次，

操作：选择区间[l,r]，将a的[l,r]区间和b的[l,r]区间的数一一对应互换

求换完之后的gcd(a1,a2,...,an)+gcd(b1,b2,...,bn)的最大值

实际t(t<=1e5)组样例，保证sumn不超过5e5

思路来源

乱搞ac+suger_fan代码

题解

固定一个端点时，另一个端点变化时，gcd只有log种，只需要考虑gcd只会变为这个端点值的因子

这个trick hdu5930用过，所以这个题做法很明显，只是不好写，码农题

不妨枚举l，注意到 gcd(a[l,r]),gcd(b[l,r]),gcd(a[r+1,n]),gcd(b[r+n]) 有一个不同的 r 只有 O(log) 个

当然枚举r也可以，这里是枚举r然后二分那log种的，复杂度O(nlog^3)，

为了快速求区间gcd所以用了st表，这里的log也考虑上gcd了

代码1（乱搞ac，ST表+二分）

#include <bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<set>
#include<array>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
const int N=2e5+10,M=20;
int t,n,lg[N];
int gcd(int x,int y){return !y?x:gcd(y,x%y);}
void init(){rep(i,2,N-5)lg[i]=lg[i>>1]+1;
}
struct RMQ{int a[N],b[N][M];void init(int n){rep(i,1,n)b[i][0]=a[i];for(int j=1;j<M;++j){for(int i=1;i+(1<<j)-1<=n;++i){b[i][j]=gcd(b[i][j-1],b[i+(1<<(j-1))][j-1]);}}}int G(int l,int r){if(l>r)return 0;int k=lg[r-l+1];return gcd(b[l][k],b[r-(1<<k)+1][k]);}
}f,g;
int main(){init();sci(t);while(t--){sci(n);rep(i,1,n)sci(f.a[i]);rep(i,1,n)sci(g.a[i]);// if(n==1){//     printf("%lld 1\n",f.a[1]+g.a[1]);//     continue;// }f.init(n);g.init(n);ll ans=0,cnt=0;rep(i,1,n){vector<array<int,5>>all;all.pb({0,0,g.G(1,i),0,f.G(1,i)});if(i>1)all.pb({1,f.G(1,1),g.G(2,i),g.G(1,1),f.G(2,i)});while(true){array<int,5>las=all.back();int l=las[0]+1,r=i-1;if(l>r)break;while(l<=r){int mid=(l+r)/2;//printf("l:%d r:%d mid:%d\n",l,r,mid);int g1=f.G(1,mid),g2=g.G(mid+1,i),g3=g.G(1,mid),g4=f.G(mid+1,i);if(array<int,4>{g1,g2,g3,g4}==array<int,4>{las[1],las[2],las[3],las[4]})l=mid+1;else r=mid-1;}if(l>=i)break;int g1=f.G(1,l),g2=g.G(l+1,i),g3=g.G(1,l),g4=f.G(l+1,i);all.pb({l,g1,g2,g3,g4});}all.pb({i,0,0,0,0});int sz=SZ(all);rep(j,0,sz-2){//printf("{%d %lld %lld}\n",all[j][0],all[j][1],all[j][2]);array<int,5>x=all[j];int g1=gcd(gcd(x[1],x[2]),f.G(i+1,n)),g2=gcd(gcd(x[3],x[4]),g.G(i+1,n));if(ans<g1+g2)ans=g1+g2,cnt=all[j+1][0]-all[j][0];else if(ans==g1+g2)cnt+=all[j+1][0]-all[j][0];//printf("i:%d pos:%d [%d,%d] g1:%d g2:%d\n",i,x[0],i,x[0],x[1],x[2]);}}printf("%lld %lld\n",ans,cnt);}return 0;
}

代码2（suger_fan代码）

很简短，直接维护所有gcd的可能性

不过复杂度没太看出来是多少，ps内也有可能有重复的，但看起来很难卡掉的样子…

from math import gcdfor _ in range(int(input())):n = int(input())a = list(map(int, input().split()))b = list(map(int, input().split()))sda, sdb = [0] * (n + 1), [0] * (n + 1)for i in reversed(range(n)):sda[i] = gcd(sda[i + 1], a[i])sdb[i] = gcd(sdb[i + 1], b[i])pda = 0pdb = 0ps = []ans, ans_c = 0, 1for i in range(n):ps.append((pda, pdb, 1))nps = []for x, y, z in ps:nps.append((gcd(x, b[i]), gcd(y, a[i]), z))nps.sort()ps.clear()for x, y, z in nps:if len(ps) == 0 or (ps[-1][0], ps[-1][1]) != (x, y):ps.append((x, y, z))else:ps[-1] = (ps[-1][0], ps[-1][1], ps[-1][2] + z)for x, y, z in ps:pans = gcd(x, sda[i + 1]) + gcd(y, sdb[i + 1])if pans > ans:ans = pansans_c = 0if pans == ans:ans_c += zpda = gcd(pda, a[i])pdb = gcd(pdb, b[i])print(ans, ans_c)