\(0,1,\ldots,X-1\) の各整数を \(M\) で割ったあまりに置き換えることを考えます。

\(M\) 個の連続する整数ごとにあまり \(0,1,\ldots,M-1\) がそれぞれ \(1\) 回ずつ現れます。したがって、\(0,1,\ldots,M-1\) という並びが \(\displaystyle \left\lfloor \frac{X}{M}\right\rfloor\) 回現れ、さらにあまりの部分として \(0,1,\ldots,X\bmod M-1\) が1回現れます。

したがって、現在の値の集合を \([0,x)\) が \(k\) 個、という形で多重集合として持つと、\(1\) 回 \(\bmod\) の演算を作用させる度に各区間は \(2\) つ以下の区間の和として表すことができます。

このシミュレーションは各区間を priority queue で保持し、さらに終端 \(x\) が同じ区間をまとめて操作することで高速に動作します。

計算量解析：

\(1\) 回 \(\bmod \ M\) の演算を作用させると、\([0,x)\) は \([0,M)\) と \(\displaystyle \left[0,x \bmod M \right)\) になります。 \([0,M)\) は全ての区間で共通です。また、\(x \bmod M\) の値は \(x\) または \(\displaystyle \frac x2\) 未満なので、\([0,M)\) を除いて考えた場合 \(1\) つの区間から生成される区間は \(O(\log x)\) 個です。

各作用で \([0,M)\) が出てくることを加味すると、priority queue の中の区間の個数は最大で \(\displaystyle O\left(N \right)\) であると評価できます。したがって、全体の計算量は \(O(N\log N\log X)\) となります。

以上を適切に実装することでこの問題に正答することができます。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
void solve() {
	int n;
	long x;
	cin >> n >> x;
	vector<long> a(n);
	for (long &v : a) cin >> v;
	priority_queue<pair<long, long>> pq;
	pq.push({x + 1, 1});
	for (long v : a) {
		while (!pq.empty() && pq.top().first > v) {
			auto [val, cnt] = pq.top();
			pq.pop();
			while (!pq.empty() && pq.top().first == val) {
				cnt += pq.top().second;
				pq.pop();
			}
			pq.push({v, val / v * cnt});
			if (val % v != 0) pq.push({val % v, cnt});
		}
	}
	long ans = -1;
	while (!pq.empty()) {
		ans += pq.top().second;
		pq.pop();
	}
	cout << ans << '\n';
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int t;
	cin >> t;
	while (t--) solve();
}

実装例(Python3)

import sys
from heapq import heappush, heappop


input = sys.stdin.readline


for _ in range(int(input())):
    n, x = map(int, input().split())
    a = list(map(int, input().split()))
    pq = [(-(x + 1), 1)]
    for v in a:
        while pq and -pq[0][0] > v:
            val, cnt = heappop(pq)
            val = -val
            while pq and -pq[0][0] == val:
                cnt += heappop(pq)[1]
            heappush(pq, (-v, (val // v) * cnt))
            if val % v:
                heappush(pq, (-(val % v), cnt))
    ans = -1
    while pq:
        ans += heappop(pq)[1]
    print(ans)