Let us consider what happens when \(0,1,\ldots,X-1\) are replaced by the remainders when they were divided by \(M\).

For each length-\(M\) chunk, the remainders \(0,1,\ldots,M-1\) occur once each. Therefore, the chunk \(0,1,\ldots,M-1\) occur \(\displaystyle \left\lfloor \frac{X}{M}\right\rfloor\) times, with the remaining chunk \(0,1,\ldots,X\bmod M-1\) once at last.

Therefore, by maintaining the set of the current values as a multiset of the form of “\(k\) copies of \([0,x)\),” each interval breaks down into the sum of at most two intervals.

This simulation runs fast enough by maintaining the intervals in a priority queue, and merging the intervals with the same ends \(x\).

Complexity analysis:

An application of the operation \(\bmod \ M\) breaks \([0,x)\) into \([0,M)\) and \(\displaystyle \left[0,x \bmod M \right)\). \([0,M)\) is shared across the intervals. Also, the value of \(x \bmod M\) is \(x\) or less than \(\displaystyle \frac x2\), so when \([0,M)\) is excluded, \(O(\log x)\) intervals are generated from an interval.

Since each action yields \([0,M)\), we can evaluate the number of intervals in a priority queue as \(\displaystyle O\left(N \right)\). Hence, the overall time complexity is \(O(N\log N\log X)\).

The problem can be solved by properly implementing this algorithm.

Sample code (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();
}

Sample code (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)