气笑了，C 放一个交互然后 D/E/F 放三个简单题。

首先注意到 $a$ 只有单调递减的一部分有用。

:::success[证明]

考虑一个 $a_i \geq a_{i-1}$。

当一个数从前面过来，一定会对 $a_{i-1}$ 取模。根据取模的性质，得到的结果一定小于 $a_{i-1}$，也就是小于 $a_i$，这样的取模是没有意义的。

:::

因此我们取 $a$ 单调递减的一部分 $b$，记 $b$ 的长度为 $k$。

考虑一个函数 f(ll v,int i) 表示 $x \in [0,v]$ 满足 $x \bmod b_{i+1} \bmod b_{i+2} \bmod b_{i+3} \bmod \ldots \bmod b_k$ 的 $x$ 的个数。一些边界条件是 $v<0$ 和 $i>k$。

显然只有满足 $b_j \leq v$ 的模数是有效的。由于 $b$ 单调递减，使用二分即可在 $O(\log k)$ 的时间内找到满足条件的第一个位置 $j$。

此时我们的 $[0,v]$ 被分成了若干段，由若干段整块和一个可能没有的零块组成。每一个整块的长度都是 $b_j$，因为在模完 $b_j$ 之后这几个整块的区间都会变成 $[0,b_j-1]$，于是答案就是 f(b[j]-1,j+1)。然后剩下一个散块答案即为 f((v+1)%b[j]-1,j+1)。

现在我们来分析时间复杂度。

由于对于确定的 $b$ 序列，我们计算整块的答案 f(b[j]-1,j+1) 是可以预处理的，并且若 $j$ 从大向小进行遍历，那么已经预处理出来的数字也可以使用。

有一个关键的观察：

(v+1)%b[j]-1 每次至少减少一半！

:::success[证明]

由于 $b_j < v$，于是可以进行分类讨论。

• $b_j \leq \frac{v}{2}$

  根据取模的性质，新的 $v’$ 一定有 $v’ < b_j \leq \frac{v}{2}$。

• $b_j > \frac{v}{2}$

  于是 $\lfloor \frac{v}{b_j} \rfloor = 1$，则 $v’ = v \bmod b_j = v - b_j < v - \frac{v}{2} = \frac{v}{2}$。

:::

因此向后搜索的深度是 $O(\log V)$ 的，单次调用复杂度 $O(\log k \log V)$，则预处理复杂度为 $O(k \log k \log V)$，查询 $O(\log k \log V)$。

:::success[code]

 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
32
33
34
35
36
37
38

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll>b;
int n,k;
ll x;
ll dp[200005];
ll dfs(ll v,int i){
	if(v<0)return 0;
	if(i>k)return 1;
	auto it=lower_bound(b.begin()+i,b.end(),v,greater<ll>());
	if(it==b.end())return 1; 
	int j=it-b.begin();
	ll ans=(v+1)/b[j]*dp[j]+dfs((v+1)%b[j]-1,j+1);
	return ans;
}
void solve(){
	scanf("%d%lld",&n,&x);
	b.clear();
    b.push_back(LONG_LONG_MAX);
	for(int i=1;i<=n;i++){
		ll ai;
		scanf("%lld",&ai);
		if(ai<b.back())b.push_back(ai);
	}
	k=b.size()-1;
	dp[k]=1;
	for(int j=k-1;j>=1;j--)dp[j]=dfs(b[j]-1,j+1);
	printf("%lld\n",dfs(x,0)-1);
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		solve();
	}
	return 0;
}

:::