题意翻译
原题链接CF2008G
思路
由于操作次数不限，观察到所有操作都是可逆的，所以可以随便搞。然后观察mex函数，发现让所有数在不重复的情况下尽可能地小是最优的（重复就浪费了）。
先不考虑重复和 0 0 0，对于 a 1 , a 2 , . . . a n a_{1}, a_{2},...a_{n} a1,a2,...an，经过无限次互相作差后，由欧几里得算法可知， g c d ( x , y ) = g c d ( x , y − x ) gcd(x, y) = gcd(x, y-x) gcd(x,y)=gcd(x,y−x)，令 g = g c d ( a 1 , . . . a n ) g=gcd(a_{1},...a_{n}) g=gcd(a1,...an)，这些数最终会变成 n n n个 g g g。
然后再调整，避免重复。当 n ≠ 1 n \neq 1 n=1，让两个 g g g相减得到 0 0 0，再把其他多余的 g g g逐个加上去，最终变成 0 , g , . . . , ( n − 1 ) g 0, g, ..., (n-1)g 0,g,...,(n−1)g。当 n = 1 n=1 n=1，动不了，特判即可。
最后，计算第 k k k个未出现过的数，观察到 i g ig ig和 ( i + 1 ) g (i+1)g (i+1)g之间由 g − 1 g-1 g−1个数未出现，所以令 m = k / ( g − 1 ) m = k / (g-1) m=k/(g−1)，即可定位到需要的数大致的位置然后分情况讨论：
（1） n = = 1 n==1 n==1， g > k − 1 g > k-1 g>k−1 ，直接取 0 → k − 1 0 \to k-1 0→k−1即可。
（2） n = = 1 n==1 n==1， g ≤ k − 1 g \le k-1 g≤k−1，取 0 , 1 , . . . g − 1 , g + 1 , . . . , k 0, 1, ... g-1, g+1, ..., k 0,1,...g−1,g+1,...,k
（3） g = = 1 g==1 g==1, 直接输出 k − 1 + n k-1+n k−1+n。这里特判是为了防止后续计算中 g − 1 = 0 g-1=0 g−1=0。
（4） n > 1 n>1 n>1, m > n − 1 m > n-1 m>n−1，说明已有的数全部被用上了，直接输出 n + k − 1 n+k-1 n+k−1
（5） n > 1 n>1 n>1, m ≤ n − 1 m \le n-1 m≤n−1, m ∗ ( g − 1 ) = = k m * (g-1) == k m∗(g−1)==k，说明恰好填满空隙，输出 k + m − 1 k+m-1 k+m−1。
（6） n > 1 n>1 n>1, m ≤ n − 1 m \le n-1 m≤n−1, m ∗ ( g − 1 ) ≠ k m * (g-1) \neq k m∗(g−1)=k，输出k+m。
分类有点繁琐，可能有几类可以通过一个式子表达。
代码
#include<bits/stdc++.h>
#define N 200005
using namespace std;
int t, n, k, a[N];
int gcd(int x, int y) {if(y == 0) return x;return gcd(y, x%y);
}
int main() {cin>>t;while(t--) {cin>>n>>k;for(int i=1;i<=n;i++) cin>>a[i];int g = a[1];for(int i=2;i<=n;i++) g = gcd(g, a[i]);// 最优0, g, 2g, ..., (n-1)g (n != 1)if(n == 1) {if(g > k-1) cout<<k-1<<endl;else cout<<k<<endl;} else if(g != 1){int m = k / (g-1); //填满m个间隙 if(m > n-1) {cout<<k-1+n<<endl;} else {if(m * (g-1) == k){ // 恰好 cout<<k+m-1<<endl;} else {cout<<k+m<<endl;}}} else {// 0, 1, 2, ..., n-1cout<<k-1+n<<endl;}}
}
