题解：CF2126E G-C-D, Unlucky!

xxxalq · 2025-07-23 20:10:24 · 题解

洛谷题目链接 & CF 题目链接

思路分析

观察分析一些性质。

一个序列的前缀或后缀的 \gcd，\operatorname{lcm}，\max，\min 都具有单调性，其中 \gcd 和 \min 单调不增，\operatorname{lcm} 和 \max 单调不降。

对于任意一个前缀 \gcd 记为 g_1,g_2,\dots,g_k 有以下性质，后缀同理。g_1=a_1，这个显然。然后就是 g_{i+1}|g_i，因为有递推式 g_{i+1}=\gcd(g_i,a_{i+1})，所以 g_{i+1} 一定是 g_1 的因数。还有一个显然的性质是 g_{k}=\gcd(a_1,a_2,\dots,a_k)，即最后一个位置的值是整个前缀的 \gcd。根据以上性质可以进行初步判定但是还没结束，随便构造几个样例就可以 hack 掉。

根据最后一条性质我们得到一些启发，在原题中 p_n=s_1=\gcd(a_1,a_2,\dots,a_n)，进一步考虑，p_i=gcd(a_1,a_2,\dots,a_i)，s_{i+1}=\gcd(a_{i+1},a_{i+2},\dots,a_n)。那么 \gcd(p_i,s_{i+1}) 就应该等于整个序列的 \gcd 也就是 p_n 和 s_1。

然后这个题就做完了。

赛时代码

//code by xxxalq
#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int maxn=100003;

int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch>57||ch<48){
        if(ch==45){
            f=-1;
        }
        ch=getchar();
    }
    while(ch>=48&&ch<=57){
        x=(x<<1)+(x<<3)+(ch-48);
        ch=getchar();
    }
    return x*f;
}

int gcd(int a,int b){
    if(b==0){
        return a;
    }
    return gcd(b,a%b);
}

int T,n,a[maxn],b[maxn];

bool solve(){
    if(a[n]!=b[1]){
        return false;
    }
    for(int i=1;i<n;i++){
        if(a[i]%a[i+1]||b[i+1]%b[i]){
            return false;
        }
        if(gcd(a[i],b[i+1])!=a[n]){
            return false;
        }
    }
    return true;
}

int main(){
    T=read();
    while(T--){
        n=read();
        for(int i=1;i<=n;i++){
            a[i]=read();
        }
        for(int i=1;i<=n;i++){
            b[i]=read();
        }
        if(n==1&&a[1]==b[1]){
            cout<<"YES\n";
            continue;
        }
//      cout<<T<<'\n';
//      if(n==2){
//          if(a[1]%a[2]==0&&b[2]%b[1]==0&&a[1]==b[2]&&a[2]==b[1]){
//              cout<<"YES\n";
//          }else{
//              cout<<"NO\n";
//          }
//          continue;
//      }
        cout<<(solve()?"YES":"NO")<<'\n';
    }
    return 0;
}