题目链接 2016 ZJCPC Problem E
考虑一个开区间$[0, x)$对$a_{i}$取模的过程。
$[0, x)$中小于$a_{i}$的部分不变，大于等于$a_{i}$的部分被切下来变成了$[0, x$ $mod$ $a_{i})$。
现在考虑开区间$[0, m+1)$，依次对$a_{1}, a_{2}, ..., a_{n}$取模。
考虑到一个数对$10^{5}$个数逐次取模，有效的取模至多$logm$次，那么同理，
这个区间最多分裂出$nlogm$个区间，这个过程用map实现（map自带平衡树的功能）。
于是处理完毕之后整个区间变成了。
$[0, c_{1})$，频数为$d_{1}$；
$[0, c_{2})$，频数为$d_{2}$；
$[0, c_{3})$，频数为$d_{2}$；
......
$[0, c_{k})$，频数为$d_{k}$；
对某个询问$y$，找到最大的$x$满足$c_{x} <= y$，那么该询问的答案即为 $\sum\nolimits_{i=x+1}^kd_i$
那么对询问离线从小到大处理即可。
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i(a); i <= (b); ++i)
#define dec(i, a, b) for (int i(a); i >= (b); --i)
#define fi first
#define se second
const int N = 1e5 + 10;
const int mod = 1e9 + 7;
typedef pair <int, int> PII;
map <int, int> mp;
map <int, int> :: iterator it;
PII a[N];
int n, m, q;
int T;
int ret, ans;
int main(){
scanf("%d", &T);
while (T--){
mp.clear();
scanf("%d%d", &n, &m);
mp[m + 1] = 1;
rep(i, 1, n){
int x;
scanf("%d", &x);
while (true){
it = mp.upper_bound(x);
if (it == mp.end()) break;
mp[x] += it -> fi / x * it -> se;
if (it -> fi % x) mp[it -> fi % x] += it -> se;
mp.erase(it);
}
}
ret = 0;
for (auto u : mp) ret += u.se;
scanf("%d", &q);
rep(i, 1, q){
scanf("%d", &a[i].fi);
a[i].se = i;
}
sort(a + 1, a + q + 1);
it = mp.begin();
ans = 0;
rep(i, 1, q){
while (a[i].fi >= it -> fi){
ret -= it -> se;
++it;
if (it == mp.end()) break;
}
if (ret == 0) break;
ans = (ans + 1ll * ret * a[i].se) % mod;
}
printf("%d\n", ans);
}
return 0;
}