贪心、动态规划、最大公约数与最小公倍数
阅读题解发现自己大错特错，学习题解做法。
序列的前缀或后缀 $\gcd$ 的取值数量为 $O(\log V)$ 等级。
假设翻转的是区间 $[l,r]$，那么 $\gcd$ 之和为
$$\gcd( \gcd\limits_{i=1}^{l-1} a_i,\gcd\limits_{i=l}^{r} b_i,\gcd\limits_{i=r+1}^{n} a_i) + \gcd( \gcd\limits_{i=1}^{l-1} b_i,\gcd\limits_{i=l}^{r} a_i,\gcd\limits_{i=r+1}^{n} b_i)$$
固定右端点 $r$，如果 $l \neq r$ 且 $\gcd\limits_{i=1}^{l-1} a_i = \gcd\limits_{i=1}^{l} a_i$ 且 $\gcd\limits_{i=1}^{l-1} b_i = \gcd\limits_{i=1}^{l} b_i$，那么翻转区间 $[l+1,r]$ 必定不劣于翻转区间 $[l,r]$。得到做法，枚举翻转右端点 $r$，然后枚举所有满足 $\gcd\limits_{i=1}^{k-1} a_i \neq \gcd\limits_{i=1}^{k} a_i$ 或 $\gcd\limits_{i=1}^{k-1} b_i \neq \gcd\limits_{i=1}^{k} b_i$ 且不超过 $r$ 的正整数 $k$ 作左端点，计算翻转后两序列 $\gcd$ 之和。
这部分的时间复杂度为 $O(n \log^2 V)$。
考虑怎么求方案数，可以在获得 $r,k$ 之后二分 $\gcd\limits_{i=l}^{r} a_i$ 和 $\gcd\limits_{i=l}^{r} b_i$ 的值不影响两序列 $\gcd$ 之和的 $l$ 的范围。这个做法的总体时间复杂度为 $O(n \log n \log^2 V)$，卡不过去。
考虑动态规划，钦定翻转区间 $l \geq 2$，这样序列 $a$ 的 $\gcd$ 只会是 $a_1$ 的因数，枚举 $a_1$ 的因数 $d$ 后可知 $b$ 的 $\gcd$ 为 $ans-d$，如果这个因数存在，则进行动态规划。
接下来动态规划求解的问题是：在 $l \geq 2$ 的情况下，选择区间 $[l,r]$ 翻转使得 $\gcd\limits_{i=1}^{n} a_i = d$ 且 $\gcd\limits_{i=1}^{n} b_i = ans - d$ 的方案数。
设计 $dp_{i,1}$ 为考虑了前 $i$ 个位置，没有选择翻转左端点的方案数；设计 $dp_{i,2}$ 为考虑了前 $i$ 个位置，已经选择了翻转左端点的方案数；设计 $dp_{i,3}$ 为考虑了前 $i$ 个位置，已经选择了翻转区间的方案数。初始化 $dp_{1,1} = 1$。
从 $i$ 向 $i+1$ 转移时只考虑两个条件：
- 若 $a_{i+1} \mid d$ 且 $b_{i+1} \mid ans-d$ 则位置 $i+1$ 可被包含在不翻转区间。
- 若 $a_{i+1} \mid ans-d$ 且 $b_{i+1} \mid d$ 则位置 $i+1$ 可被包含在翻转区间。
此外转移应该在分类讨论三种情况，最后一种情况容易被忽略：
- 选定 $l$，即从当前位置开始翻转；
- 选定 $r$，即在当前位置结束翻转；
- 同时选定 $l,r$，即翻转一个长度为 $1$ 的区间，必须单独转移。
动态规划得到的方案必定满足 $\gcd\limits_{i=1}^{n} a_i = d$ 且 $\gcd\limits_{i=1}^{n} b_i = ans-d$，考虑如下事实：
- 如果动态规划得到的方案中 $\gcd\limits_{i=1}^{n} a_i$ 与 $\gcd\limits_{i=1}^{n} b_i$ 其中一个值不变，另一个值增加。那么 $ans$ 的值就不是所有翻转方案中最大的，矛盾。
- 如果动态规划得到的方案满足 $ans$ 最优，但 $\gcd\limits_{i=1}^{n} a_i \neq d$ 或 $\gcd\limits_{i=1}^{n} b_i \neq ans-d$。由于动态规划保证对应序列的 $\gcd$ 不小于指定值，而出现此种情况必定会导致存在一个值比指定值更小，矛盾。
分析时间复杂度，首先是 $O(\sqrt{V})$ 的质因数分解，然后动态规划的时间复杂度有宽松的上界 $O(nd(V))$，理论可过。
注意动态规划求的是 $l \geq 2$ 的方案数，枚举一遍翻转 $[1,i]$ 的方案加入方案数中才是全部方案数。
单个测试点总体时间复杂度 $O(n \log^2 V + n d(V) + \sqrt{V})$。
结果跑得还不如三个 $\log$ 的做法快，考虑为啥，发现最坏情况下 $O(T \sqrt{V})$ 的计算量过大。对于 $n$ 比较小的情况跑 $O(n^2 \log n)$ 暴力就可以避免 $O(\sqrt{V})$ 分解质因数了。
#include<bits/stdc++.h>
#define ctz __builtin_ctz
using namespace std;
int n,ans,cnt,p[105],prea[200'005],preb[200'005],sufa[200'005],sufb[200'005],a[20][200'005],b[20][200'005];
long long sum;
inline int abs(int x){return x<0 ? -x:x;}
inline int min(int x,int y){return x<y ? x:y;}
inline int max(int x,int y){return x<y ? y:x;}
inline int gcd(int x,int y){
static int d,ox,oy,ret;
if(x==0||y==0) return x|y;
ox=ctz(x),oy=ctz(y);
y>>=oy,ret=min(ox,oy);
while(x){
x>>=ox,d=abs(x-y);
if(d) ox=ctz(d);
y=min(x,y),x=d;
}
return y<<ret;
}
inline int query(int l,int r,int (*x)[20'0005]){
int o=__lg(r-l+1);
return gcd(x[o][l],x[o][r-(1<<o)+1]);
}
inline int rev(int l,int r){
int ra=query(l,r,b),rb=query(l,r,a);
if(l!=1) ra=gcd(ra,prea[l-1]),rb=gcd(rb,preb[l-1]);
if(r!=n) ra=gcd(ra,sufa[r+1]),rb=gcd(rb,sufb[r+1]);
return ra+rb;
}
long long calculate(int x,int y){
static long long dp[200'005][4];
for(int i=1;i<=n;i++) dp[i][1]=0ll,dp[i][2]=0ll,dp[i][3]=0ll;
dp[1][1]=1ll;
for(int i=2;i<=n;i++){
if(a[0][i]%x==0&&b[0][i]%y==0){
dp[i][1]+=dp[i-1][1];
dp[i][3]+=dp[i-1][3];
}
if(a[0][i]%y==0&&b[0][i]%x==0){
dp[i][2]+=dp[i-1][1];
dp[i][2]+=dp[i-1][2];
dp[i][3]+=dp[i-1][1];
dp[i][3]+=dp[i-1][2];
}
}
return dp[n][3];
}
void force_solution(){
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++) if(rev(i,j)==ans) ++sum;
cout<<ans<<' '<<sum<<'\n';
}
void solution(){
cin>>n,ans=0,cnt=0,sum=0ll;
for(int i=1;i<=n;i++) cin>>a[0][i];
for(int i=1;i<=n;i++) cin>>b[0][i];
prea[1]=a[0][1],preb[1]=b[0][1];
for(int i=2;i<=n;i++){
prea[i]=gcd(prea[i-1],a[0][i]);
preb[i]=gcd(preb[i-1],b[0][i]);
}
sufa[n]=a[0][n],sufb[n]=b[0][n];
for(int i=n-1;i>=1;i--){
sufa[i]=gcd(sufa[i+1],a[0][i]);
sufb[i]=gcd(sufb[i+1],b[0][i]);
}
for(int i=1;(1<<i)<=n;i++)
for(int j=1;j+(1<<i)-1<=n;j++) a[i][j]=gcd(a[i-1][j],a[i-1][j+(1<<(i-1))]);
for(int i=1;(1<<i)<=n;i++)
for(int j=1;j+(1<<i)-1<=n;j++) b[i][j]=gcd(b[i-1][j],b[i-1][j+(1<<(i-1))]);
p[++cnt]=1;
for(int i=2;i<=n;i++) if(prea[i]!=prea[i-1]||preb[i]!=preb[i-1]) p[++cnt]=i;
for(int i=1;i<=n;i++){
for(int j=1;j<=cnt&&p[j]<=i;j++) ans=max(ans,rev(p[j],i));
ans=max(ans,rev(i,i));
}
if(n<=500) return force_solution();
for(int i=1;i<=n;i++) if(rev(1,i)==ans) ++sum;
for(int i=1;i*i<=a[0][1];i++) if(a[0][1]%i==0){
int x=i,y=ans-x;
if(y>=1&&b[0][1]%y==0) sum+=calculate(x,y);
if(i*i==a[0][1]) continue;
x=a[0][1]/i,y=ans-x;
if(y>=1&&b[0][1]%y==0) sum+=calculate(x,y);
}
cout<<ans<<' '<<sum<<'\n';
}
int T;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>T;
while(T--) solution();
return 0;
}这里放一下之前的思维过程。
首先解决第一个问题：求出执行一次交换后 $\gcd\limits_{i=1}^{n} a_i + \gcd\limits_{i=1}^{n} b_i$ 的值最大是多少。
钦定 $a_1$ 和 $b_1$ 不被交换，也就是说固定它们的位置，那么 $\gcd\limits_{i=1}^{n} a_i$ 必定为 $a_1$ 的因数，$\gcd\limits_{i=1}^{n} b_i$ 必定为 $b_1$ 的因数。
这里又牵扯到约数个数了，查表发现 $\max\limits_{i=1}^{10^9} d(i) = 1344$，由于判定某个因数是否可以成为最终序列的最小公因数很可能需要枚举整个序列，复杂度大概是要乘上一个 $n$ 的，所以能接受的也只是枚举 $a_1$ 的所有因数。
枚举 $a_1$ 的因数 $k$ 后从 $2$ 到 $n$ 遍历正整数 $i$，分类讨论。
- 如果 $a_i$ 和 $b_i$ 都不是 $k$ 的倍数则说明 $k$ 不能成为序列 $a$ 的全局 $\gcd$。
- 如果 $a_i$ 和 $b_i$ 中有一个数是 $k$ 的倍数，如果这个数是 $b_i$ 就必须交换 $a_i,b_i$ 来保证 $k$ 是 $a$ 的全局 $\gcd$，反之则不能交换 $a_i,b_i$。
- 如果 $a_i,b_i$ 都是 $k$ 的倍数，那么交换 $a_i,b_i$ 是可选的。
标记必须交换的位置、不能交换的位置和可选择交换的位置，通过最左边和最右边必须交换的位置确定最短的必须被交换的区间。这个区间中存在不能交换的位置则 $k$ 不能成为序列 $a$ 的全局 $\gcd$。否则，设 $[l,r]$ 为最短的必须交换的区间，先完成交换。
交换后维护能够成为序列 $b$ 全局 $\gcd$ 的数的集合，依次枚举 $1 \sim n$ 中的每个整数，枚举集合中的每个数 $x$，分类讨论。
- 能够交换 $a_i,b_i$ 时（注意如果 $i \in [l,r]$ 则不能交换）若 $a_i,b_i$ 都不是 $x$ 的倍数则 $x$ 不能成为 $b$ 的全局 $\gcd$，将其从集合中删去。
- 否则若 $b_i$ 不是 $x$ 的倍数则 $x$ 不能成为 $b$ 的全局 $\gcd$，将其从集合中删去。
最后集合中最大的数是 $\gcd\limits_{i=1}^{n} a_i = k$ 的情况下能得到的 $\gcd\limits_{i=1}^{n} b_i$ 的最大值。
时间复杂度 $O(n d(V)^2 \log d(V))$ 显然跑不过四秒时限。