数学、贪心、最大公约数与最小公倍数

如果环 $i$ 的可拨动范围 $r_i - l_i +1 \geq x$，那么 $[l_i,r_i]$ 中肯定存在一个 $x$ 的倍数。如果所有环的长度都不小于 $k$，那么显然存在让最终所有数 $\gcd$ 等于 $k$ 的解。

否则必定存在一个长度小于 $k$ 的环，枚举其中所有数字进行质因数分解，选出所有不小于 $k$ 的因数 $x$，然后 $O(n)$ 判断是否存在 $\gcd = x$ 的解。

时间复杂度 $O(n k d(V) + k \sqrt{V})$，其中 $O(n k d(V))$ 本身跑不满，加上因数大小不小于 $k$ 的限制后程序常数更小，可以在 250ms 内跑过所有测试点。

#include<bits/stdc++.h>
using namespace std;
int n,k,l[10'005],r[10'005];
bool success(int x){
    for(int i=1;i<=n;i++) if((l[i]+x-1)/x*x>r[i]) return 0;
    return 1;
}
void answer(int x){
    cout<<"Yes"<<'\n';
    for(int i=1;i<=n;i++) cout<<(l[i]+x-1)/x*x<<" \n"[i==n];
}
void force(int x){
    unordered_set<int> s;
    for(int i=l[x];i<=r[x];i++){
        int lim=__builtin_sqrt(i);
        for(int j=1;j<=lim;j++) if(i%j==0){
            if(j>=k) s.emplace(j);
            if(i/j>=k) s.emplace(i/j);
        }
    }
    for(int i:s) if(success(i)) return answer(i);
    cout<<"No"<<'\n';
}
void solution(){
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>l[i]>>r[i];
    for(int i=1;i<=n;i++) if(r[i]-l[i]+1<k) return force(i);
    cout<<"Yes"<<'\n';
    for(int i=1;i<=n;i++) cout<<(l[i]+k-1)/k*k<<" \n"[i==n];
}
int T;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--) solution();
    return 0;
}