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

操作可以让序列中任意两个数相减，符合更相减损术的形式。

注意到任意次操作后序列中仅能存在全局 $\gcd$ 的倍数，令全局 $\gcd$ 为 $X$，那么 $\operatorname{mex}_k$ 每隔 $X$ 个数能被序列中的数抵消一个，有 $k-1$ 次接续答案的机会，容易计算答案。注意如果 $n \neq 1$ 那么肯定能让序列中的元素变成 $0$，但是 $n=1$ 时不能让序列中的元素变成 $0$，应当单独处理。

时间复杂度 $O(n + \log V)$。

#include<bits/stdc++.h>
using namespace std;
int n,m,k,ans;
void solution(){
    cin>>n>>k>>m,--k;
    if(n==1){
        if(m<=k) ans=k+1;
        else ans=k;
        return cout<<ans<<'\n',void();
    }
    ans=1;
    for(int i=1;i<=n-1;i++){
        static int x;
        cin>>x,m=__gcd(m,x);
    }
    for(int i=1;i<=n-1;i++) if(k>=m-1) ans+=m,k-=m-1;
    ans+=k;
    cout<<ans<<'\n';
}
int T;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--) solution();
    return 0;
}