Codeforces Round 970 (Div. 3) G. Sakurako's Task 题解

2025 年 01 月 11 日

68 次浏览

1438字数

# 题目描述

给定长度为 $n$ 的正整数序列 $a$。定义一次操作为：选择 $i,j$ 满足 $i \ne j$ 且 $a_i \ge a_j$，令 $a_i = a_i - a_j$ 或 $a_i = a_i + a_j$。求操作任意次后最大可能的 $mex_k$。

$mex_k$ 是序列中不存在的第 $k$ 个自然数。例如，$mex_1(\{1,2,3 \})=0$，因为 $0$ 是第 $1$ 个不在数组中的元素，而 $mex_2(\{0,2,4 \})=3$，因为 $3$ 是第 $2$ 个不在数组中的元素。

# 输入

**输入**

第一行包含一个整数 $t$ ($1\le t\le 10^4$)  — 测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $k$ ($1\le n\le 2\cdot 10^5,1\le k\le 10^9$)  — 数组中元素的个数和 $mex_k$ 的值。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots,a_n$ ($1\le a_i\le 10^9$)  — 数组的元素。

保证所有测试用例中 $n$ 的总和不超过 $2\cdot 10^5$。

## 输出格式

对于每个测试用例，输出最大 $mex_k$;这可以通过操作来实现。

## 解题思路

看到题目描述类似于辗转相减， 尝试向辗转相减法去靠：

- 为了满足题意， **数组应该越小越好**
- 对于$n=1$的情况可以单独讨论
- 假设对于 $i,j$ 满足 $i \ne j$ 且 $a_i \ge a_j$，令 $a_i^{'} = a_i - a_j$, 设$\exists d, d|a_i \wedge d|a_j$, 显然有$d|a_i^{'}$
- 同理， 假设对于 $i,j$ 满足 $i \ne j$ 且 $a_i \ge a_j$，令 $a_i^{'} = a_i + a_j$， 也有上述结论
- 因此无论如何修改上述数组， 其每个元素都是所有元素的最大公约数的倍数， 设最大公约数为$d$, 则数组最小可以是$0, d, 2d, \dots , nd$

## AC代码

```cpp
#include <cstdio>
#include <cstdlib>
#include <iostream>
#define endl '\n'
using namespace std;
const int N = 2e5 + 10;
int t;
int n, k;
int a[N];

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> t;
    while(t --)
    {
        cin >> n >> k;
        for(int i = 1; i <= n; i ++) cin >> a[i];
        if(n < 2)
        {
            if(a[1] >= k)
            {
                cout << k - 1 << endl;
            }
            else
            {
                cout << k << endl;
            }
        }
        else
        {
            int tmp = gcd(a[1], a[2]);
            for(int i = 3; i <= n; i ++)
            {
                tmp = gcd(tmp, a[i]);
            }
            if(tmp == 1)
            {
                cout << n + k - 1 << endl;
            }
            else
            {
                if(1ll * (n - 1) * (tmp - 1) >= k)
                {
                    int tt = k / (tmp - 1);
                    int ans = tt * tmp - 1;
                    if(k % (tmp - 1))
                    {
                        ans += 1 + (k % (tmp - 1));
                    }
                    cout << ans << endl;
                }
                else
                {
                    cout << n + k - 1 << endl;
                }
            }
        }
    }
	return 0;
}
```

最后修改：2025 年 01 月 11 日