AtCoder Beginner Contest 466

“You have to give up some of the old so that you can make room for the new.”

— Yanni

首页 » 题解 » AtCoder » AtCoder Beginner Contest 466

一些废话

$OMG$ ，俺的超绝猜题能力又发挥作用了，这次的 $E$ 很典，是一道很典的背包问题，但是我一直被卡在初始化，我最开始都初始化为 $0$ ，然后与样例答案差一，我就开始猜了，因为只剩两分钟了，没时间细想，改了一下初始化就过了。 $D$ 也是一道很典的题，你只要做过并查集，这个很像逆向运用并查集的思路，也是倒着做。 $C$ 是真的恶心，我想到了用双指针，但是由于一直都写不好双指针，总是容易写出锅，范围没框对啊，有些细节没考虑到啊，数组越界了啊，等等。还有就是我算这个会不会超 $2n$ 也算了挺久。然后 $A ，B$ 就没什么好说的，各凭手速，不对，网速

Contents hide

3 B – Representative Balls

3.1 题意

3.2 思路

3.3 代码

4 C – Count Close Pairs

7 F – Many Mod Calculation

7.1 题意

7.2 思路

7.3 代码

A – Compromise

题意

给出一个数组 $x$ ，若无论你选哪个数，都是负数，则输出 $Yes$ ，否则输出 $No$

思路

判断是否全是负数

代码

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;

void solve() {
    int n;
    cin >> n;

    int f = 0;
    for (int i = 1; i <= n; ++i) {
        int x;
        cin >>x;
        if (x >= 0) {
            f = 1;
        }
    }

    if (f) {
        cout << "No" << endl;
    }
    else {
        cout << "Yes" << endl;
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    LL T = 1;
    //cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;

void solve() {
    int n;
    cin >> n;

    int f = 0;
    for (int i = 1; i <= n; ++i) {
        int x;
        cin >>x;
        if (x >= 0) {
            f = 1;
        }
    }

    if (f) {
        cout << "No" << endl;
    }
    else {
        cout << "Yes" << endl;
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    LL T = 1;
    //cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

B – Representative Balls

题意

有 $n$ 个球，第 $i$ 个球的颜色为 $c_i$ ，大小为 $s_i$ ，有 $m$ 种颜色，对于第 $k$ 种颜色来说，球的最大值为多少，若没有对应颜色的球，则输出 $-1$ ， $k = 1, 2, 3 \ .\ .\ .\ m$

思路

每种颜色初始化为 $-1$ ，然后保存其出现过的颜色对应的球的最大值

代码

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;

void solve() {
    int n, m;
    cin >> n >> m;

    vector<int> a(m + 1, -1);

    for (int i = 1;i <= n; ++i) {
        int c, w;
        cin >> c >> w;
        a[c] = max(a[c], w);
    }

    for (int i = 1; i <= m; ++i) {
        cout << a[i] << " ";
    }
    cout << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    LL T = 1;
    //cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;

void solve() {
    int n, m;
    cin >> n >> m;

    vector<int> a(m + 1, -1);

    for (int i = 1;i <= n; ++i) {
        int c, w;
        cin >> c >> w;
        a[c] = max(a[c], w);
    }

    for (int i = 1; i <= m; ++i) {
        cout << a[i] << " ";
    }
    cout << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    LL T = 1;
    //cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

C – Count Close Pairs

题意

在一个数轴上有 $n$ 个点，分别按 $1， 2， 3 \ .\ .\ . \ n$ 的顺序依次排列，每次你可任意询问两个点之间的距离是否最多为 $1$ ，询问次数最多为 $2n$ 次，输出两点之间距离最多为 $1$ 的点的对数

思路

呃，我看了一下官方题解，我好像想复杂了，我居然用了一点容斥，我他妈就说嘛，一道 $C$ 这么可能难成那样，原来都是自己给自己上难度

我就不讲我的复杂思路了，讲官方题解的思路吧

${\color{Yellow}双指针}$

首先，我们知道一点，对于第 $i$ 个点来说，假设他与 $i + 1, i + 2, i + 3, \ .\ .\ . \ j$ 都满足两点距离最多为 $1$ ，则对于第 $i + 1$ 个点来说，他更加满足与 $i +2, i +3,\ .\ . \ . \ j$ 的两点间距离最多为 $1$ ，所以，当我们找到一个满足条件的区间，即 $L = i, R = j$ , 之后 ${L}’ = i +1, \ R’ \geq R = j$ ，左右端点都只会往一个方向移动，所以可以用双指针来实现

当 $L= R$ 时， $R$ 往右移一格（这个很重要，不写会 $WA$ ，我只知道应该是超过了 $2n$ ，但我不会算）

当 $L < R$ 时，直到 $R$ 不满足与 $L$ 两点之间距离的最多为 $1$ 而停下来。若 $R= n + 1$ ，则退出，剩下的 $L$ 都对应该固定的 $R$ ；若 $R \leq n$ , 则答案加上 $R – L – 1$ （固定左端点，变化右端点）

代码

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
// #define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;

void solve() {
    int n;
    cin >> n;

    auto ask = [&](int i, int j)
    {
        cout << "? " << i << " " << j << endl;
        string s;
        cin >> s;
        return s;
    };

    int ans = 0;
    for (int i = 1, j = 2; i <= n; ++i) {
        j = max(i + 1, j);
        while (j <= n && ask(i, j) == "Yes") {
            ++j;
        }
        ans += j - i - 1;
    }

    cout << "! " << ans << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    LL T = 1;
    //cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
// #define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;

void solve() {
    int n;
    cin >> n;

    auto ask = [&](int i, int j)
    {
        cout << "? " << i << " " << j << endl;
        string s;
        cin >> s;
        return s;
    };

    int ans = 0;
    for (int i = 1, j = 2; i <= n; ++i) {
        j = max(i + 1, j);
        while (j <= n && ask(i, j) == "Yes") {
            ++j;
        }
        ans += j - i - 1;
    }

    cout << "! " << ans << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    LL T = 1;
    //cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

我当时过题的代码

还是贴一下吧，万一有脑回路清奇的同道中人看得懂呢

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;

void solve()
{
    int n;
    cin >> n;

    int f = 0;
    auto ask = [&](int i, int j)
    {
        cout << "? " << i << " " << j << endl;
        string s;
        cin >> s;
        if (s == "Yes") {
            f = 1;
        }
        return s;
    };

    int ans = 0, pre = -1;
    for (int i = 1, j = 2; i <= n && j <= n; ++i)
    {
        if (j == i) {
            ++j;
        }
        f = 0;
        while (j <= n && ask(i, j) == "Yes")
        {
            ++j;
        }
        if (f) {
            int k = j - i - 1;
            ans += k * (k + 1) / 2;
            if (i <= pre)
            {
                int k = pre - i;
                ans -= k * (k + 1) / 2;
            }
        }
        pre = j - 1;
    }

    cout << "! " << ans << endl;
}

signed main()
{
    // ios::sync_with_stdio(false);
    // cin.tie(0); cout.tie(0);

    LL T = 1;
    // cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;

void solve()
{
    int n;
    cin >> n;

    int f = 0;
    auto ask = [&](int i, int j)
    {
        cout << "? " << i << " " << j << endl;
        string s;
        cin >> s;
        if (s == "Yes") {
            f = 1;
        }
        return s;
    };

    int ans = 0, pre = -1;
    for (int i = 1, j = 2; i <= n && j <= n; ++i)
    {
        if (j == i) {
            ++j;
        }
        f = 0;
        while (j <= n && ask(i, j) == "Yes")
        {
            ++j;
        }
        if (f) {
            int k = j - i - 1;
            ans += k * (k + 1) / 2;
            if (i <= pre)
            {
                int k = pre - i;
                ans -= k * (k + 1) / 2;
            }
        }
        pre = j - 1;
    }

    cout << "! " << ans << endl;
}

signed main()
{
    // ios::sync_with_stdio(false);
    // cin.tie(0); cout.tie(0);

    LL T = 1;
    // cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

D – Placing Rooks

题意

有一个 $n$ 行 $n$ 列的棋盘，给出 $m$ 条信息，每次给出 $r_i$ 行， $c_i$ 列，代表先将 $r_i$ 行和 $c_i$ 列都清空，然后在 $(r_i, c_i)$ 处放置一个棋子，问最后棋盘上有多少个棋子

思路

${\color{Yellow}正难则反}$

正着思考就只有模拟， $O(nm)$ 肯定会超时的，逆着思考，讨论从第 $m$ 条信息到第 $1$ 条信息，若在 $(r_i, \ c_i)$ 处放置了一颗棋子，说明第 $r_i$ 行，和 $c_i$ 列就被限制了，那么“之后”不可再放置棋子。有一点需要注意，若讨论到第 $r_j$ 行 , $c_j$ 列时，若其行在之前已经被限制了，则该棋子不可被加入到答案中，但并不是就直接跳过了，而是他的列 $c_j$ 也要对“之后”的棋子产生限制，因为对于之前的棋子来说，他的的确确是放进来了的，并且是的的确确覆盖了之前的行与列的，我交的第一发 $WA$ 了就是忘了这个限制，直接无脑跳过

代码

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;

void solve()
{
    LL n, m;
    cin >> n >> m;

    vector<LL> x(m + 1), y(m + 1);
    for (LL i = 1; i <= m; ++i)
    {
        cin >> x[i] >> y[i];
    }

    map<LL, LL> r, c;
    LL ans = 0;
    for (LL i = m; i >= 1; --i)
    {
        if (!r.count(x[i]) && !c.count(y[i]))
        {
            ++ans;
        }
        r[x[i]] = 1;
        c[y[i]] = 1;
    }

    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    LL T = 1;
    // cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;

void solve()
{
    LL n, m;
    cin >> n >> m;

    vector<LL> x(m + 1), y(m + 1);
    for (LL i = 1; i <= m; ++i)
    {
        cin >> x[i] >> y[i];
    }

    map<LL, LL> r, c;
    LL ans = 0;
    for (LL i = m; i >= 1; --i)
    {
        if (!r.count(x[i]) && !c.count(y[i]))
        {
            ++ans;
        }
        r[x[i]] = 1;
        c[y[i]] = 1;
    }

    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    LL T = 1;
    // cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

E – Range Flip

题意

有 $n$ 张扑克牌，第 $i$ 张扑克牌正面写着 $a_i$ , 背面写着 $b_i$ ，你最多有 $k$ 次翻牌的机会，每次可选择区间 $[l, r]$ 翻牌， $1 \leq l \leq r \leq n$ ，问最后纸牌朝上一面上的牌值之和最大为多少

思路

${\color{Yellow}动态规划（背包问题）}$

最多有 $k$ 次翻牌机会，等同于最多有 $k$ 个 $b$ 区间可取代 $a$ 区间，即使你中间有翻重的，但最后整体显示的就是这个结果，什么意思呢？就比如你先翻 $L = 2, R = 9$ ，然后翻 $L = 4, R = 7$ ，形成了两个区间，等同于你先翻 $L = 2, R = 3$ , 然后翻 $L = 8, R = 9$ ，这是包含的情况。但即使是相交，也是同样，就比如你先翻 $L = 2, R = 7$ , 然后翻 $L = 5, R = 10$ ，等同于你先翻 $L = 2, R = 4$ , 然后翻 $L = 8, R = 10$ ，同样也是翻两次，形成两个区间

然后最开始朝上的面都为 $a$ ，我们就假设先全都选 $a$ ， $sm = \sum_{i = 1}^n a_i$ ，令数组 $c_i = b_i – a_i$ ，若 $sm += c_i$ ，则等同于将 $a_i$ 换成 $b_i$ ，而最开始 $sm = \sum_{i = 1}^n a_i$ 是固定的，其等同于一次牌也不翻，决定最后 $sm$ 大小的因素是所选择的 $c_i$ 的和，所以该问题就变成了背包问题，选与不选，其加的唯一一个限制就是最多可选择 $k$ 个连续区间

设 $dp[i][j][k]$ ：讨论到第 $i$ 个数，已形成 $j$ 个连续区间， $k = 0$ 是不选 $c_i$ ，反之则选

代码

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;

void solve() {
    LL n, m;
    cin >> n >> m;

    vector<LL> a(n + 1, 0), b(n + 1, 0), c(n+ 1, 0);
    LL sm = 0;
    for (LL i = 1; i <= n; ++i) {
        cin >> a[i] >> b[i];
        c[i] = b[i] - a[i];
        sm += a[i];
    }

    vector<vector<vector<LL>>> dp(n + 2, vector<vector<LL>> (m + 1, vector<LL>(2, -INF)));

    dp[0][0][0] = 0;
    for (LL i = 1; i <= n; ++i) {
        for (LL j = 0; j <= m; ++j) {
            dp[i][j][0] = max(dp[i - 1][j][1], dp[i - 1][j][0]);
            if (j > 0) {
                dp[i][j][1] = max(dp[i][j][1], dp[i - 1][j - 1][0] + c[i]);
            }
            dp[i][j][1] = max(dp[i][j][1], dp[i - 1][j][1] + c[i]);
        }
    }

    LL ans = 0;
    for (LL i = 0; i <= m; ++i) {
        for (LL k = 0; k <= 1; ++k) {
            ans = max(ans, dp[n][i][k]);
        }
    }

    cout << ans + sm << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    LL T = 1;
    //cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;

void solve() {
    LL n, m;
    cin >> n >> m;

    vector<LL> a(n + 1, 0), b(n + 1, 0), c(n+ 1, 0);
    LL sm = 0;
    for (LL i = 1; i <= n; ++i) {
        cin >> a[i] >> b[i];
        c[i] = b[i] - a[i];
        sm += a[i];
    }

    vector<vector<vector<LL>>> dp(n + 2, vector<vector<LL>> (m + 1, vector<LL>(2, -INF)));

    dp[0][0][0] = 0;
    for (LL i = 1; i <= n; ++i) {
        for (LL j = 0; j <= m; ++j) {
            dp[i][j][0] = max(dp[i - 1][j][1], dp[i - 1][j][0]);
            if (j > 0) {
                dp[i][j][1] = max(dp[i][j][1], dp[i - 1][j - 1][0] + c[i]);
            }
            dp[i][j][1] = max(dp[i][j][1], dp[i - 1][j][1] + c[i]);
        }
    }

    LL ans = 0;
    for (LL i = 0; i <= m; ++i) {
        for (LL k = 0; k <= 1; ++k) {
            ans = max(ans, dp[n][i][k]);
        }
    }

    cout << ans + sm << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    LL T = 1;
    //cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

F – Many Mod Calculation

题意

给出大小为 $n$ 的数组 $a$ 和一个整数 $X$ ，对于 $f(x)$ 有以下定义：

$f(x)= ((((x \ mod \ a_1) \ mod \ a_2 ) \ mod \ a_3) …) \ mod \ a_n$ ，问 $1$ 到 $X$ 中有多少个整数满足 $f(x) = 0$

思路

讨论 $a_i$ : 对于一个数 $x$ ，模上 $a_i$ ，若 $x \leq a_i$ , 剩余的数一定会被分成两部分，一部分是 $[0, a_i – 1]$ ，另一部分是 $[1, x \ mod \ a_i]$ ，第一部分此时已经有 $0$ ，将 $0$ 的个数加入到答案中，然后排除掉 $0$ ，变为 $[1, a_i – 1]$ 。

讨论 $a_j \ (j = i +1)$ : 分别将刚刚的两部分剩余的结果模上 $a_j$ ，若 $a_j \leq a_i – 1$ ，则 $[1, a_i – 1]$ 又会被分成两部分，分别为 $[0, a_j – 1], [1, a_j \ mod \ (a_i – 1)]$ ，此时又出现了 $0$ ，将 $0$ 加入到答案中，并去除掉，变为 $[1, a_j – 1]$ ，再考虑刚刚剩余的另一部分，若 $(x \ mod \ a_i) \leq a_j$ ，则继续将其分成两部分， $[0, a_j – 1], [1, (x \ mod \ a_i) \ mod \ a_j]$ ，同理，也是去除掉 $0$ ，变为 $[1, a_j – 1]$ 。发现，每次都是会被分成商的部分和余数的部分，而商的部分一定包含 $0$ ，此时就可以加入到答案中。

呃，我感觉没讲清楚，举个例子：

n = 3, x = 17
5 2 3

17 >= 5
p = 17 / 5 = 3
r = 17 % 5 = 2
[1, 17] -> 
0 1 2 3 4
0 1 2 3 4
0 1 2 3 4
1 2
把 0 加入到答案中，变成
1 2 3 4
1 2 3 4
1 2 3 4
1 2

4 >= 2, 2 >= 2
p = 4 / 2 = 2
r = 4 % 2 = 0
3 * [1, 4] + 1 * [1, 2] ->
0 1 2 
0 1 2
0 1 2
0 1 2
0 1 2
0 1 2
1 2
把 0 加入到答案中，得
1 2
1 2
1 2
1 2
1 2
1 2
1 2

2 < 3
跳过，因为之后再怎么除都无法得余数为零

我们发现每次处理的区间都是 $cnt \.\ [1, num]，$ 所以我们只保存 $cnt, \ num$ ，用优先队列保存。

若 $num \geq a_i$ ， $num \div a_i = p . . . r$

商的部分 $\ [0, \ a_i – 1] \.\ p$ ，再考虑本身就有 $cnt$ 个，所以该部分为 $[0, \ a_i – 1] \.\ p \.\ cnt$ ，答案加上 0 的个数 $p \.\ cnt$ ，该部分变为 $[1, \ a_i – 1] \.\ p \.\ cnt$ ，若 $a_i – 1 \geq 0$ ，则将该部分加入到优先队列中

余数部分 $[1, r]$ ，再考虑本身就有 $cnt$ 个，所以该部分为 $[1, \ r] \.\ cnt$ ，若 $r \geq 0$ ，则将该部分加入到优先队列中

代码

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;

void solve() {
    LL n, x;
    cin >> n >> x;

    vector<LL> a;
    for (LL i = 1; i <= n; ++i) {
        LL t;
        cin >> t;
        if (!a.empty() && a.back() <= t) {
            continue;
        }
        a.push_back(t);
    }

    priority_queue<PLL> q;
    q.push({x, 1});

    n = a.size();
    LL ans = 0;
    for (LL i = 0; i < n; ++i) {
        while (!q.empty() && q.top().first >= a[i]) {
            auto [num, cnt] = q.top();
            q.pop();
            while (!q.empty() && q.top().first == num) {
                auto [_, tot] = q.top();
                q.pop();
                cnt += tot;
            }
            LL p = num / a[i];
            LL r = num % a[i];
            ans += p * cnt;
            if (a[i] > 1) {
                q.push({a[i] - 1, p * cnt});
            }
            if (r > 0) {
                q.push({r, cnt});
            }
        }
    }

    cout << ans << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    LL T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;

void solve() {
    LL n, x;
    cin >> n >> x;

    vector<LL> a;
    for (LL i = 1; i <= n; ++i) {
        LL t;
        cin >> t;
        if (!a.empty() && a.back() <= t) {
            continue;
        }
        a.push_back(t);
    }

    priority_queue<PLL> q;
    q.push({x, 1});

    n = a.size();
    LL ans = 0;
    for (LL i = 0; i < n; ++i) {
        while (!q.empty() && q.top().first >= a[i]) {
            auto [num, cnt] = q.top();
            q.pop();
            while (!q.empty() && q.top().first == num) {
                auto [_, tot] = q.top();
                q.pop();
                cnt += tot;
            }
            LL p = num / a[i];
            LL r = num % a[i];
            ans += p * cnt;
            if (a[i] > 1) {
                q.push({a[i] - 1, p * cnt});
            }
            if (r > 0) {
                q.push({r, cnt});
            }
        }
    }

    cout << ans << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    LL T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

一	二	三	四	五	六	日
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30	31