zoj 3940 dp

One day, Peter came across a function which looks like:
F(1, X) = X mod A1. F(i, X) = F(i - 1, X) mod Ai, 2 ≤ i ≤ N. Where A is an integer array of length N, X is a non-negative integer no greater than M. Peter wants to know the number of solutions for equation F(N, X) = Y, where Y is a given number.
Input There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:
The first line contains two integers N and M (2 ≤ N ≤ 105, 0 ≤ M ≤ 109).
The second line contains N integers: A1, A2, …, AN (1 ≤ Ai ≤ 109).
The third line contains an integer Q (1 ≤ Q ≤ 105) - the number of queries. Each of the following Q lines contains an integer Yi (0 ≤ Yi ≤ 109), which means Peter wants to know the number of solutions for equation F(N, X) = Yi.
Output For each test cases, output an integer S = (1 ⋅ Z1 + 2 ⋅ Z2 + … + Q ⋅ ZQ) mod (109 + 7), where Zi is the answer for the i-th query.
Sample Input 1 3 5 3 2 4 5 0 1 2 3 4 Sample Output 8 Hint The answer for each query is: 4, 2, 0, 0, 0. 제목: 한 조의 수를 제시하고 현재 하나의 수 x를 정하면 하나의 값 x%a1%a2,,,%an을 얻을 수 있다. 먼저 q개의 질문 y를 주고 각 질문마다 몇 개의 x(1-m 사이)를 추출하면 y에 도착할 수 있는지 묻는다.방법: 숫자를 단계별로 나누어 이런 이원조를 기록한다.

#include
using namespace std;
const int N = 1e5+100;
const int mod = 1e9+7;
map<int,int> mp;
int pos[N];
int sum[N];
int n,m;
int main(){
    int T;
    cin >> T;
    while(T--){
        int n,m;
        scanf("%d %d",&n,&m);
        mp.clear();
        mp[m] = 1;
        for(int i = 1;i <= n;i ++){
            int now;
            scanf("%d",&now);
            auto iter = mp.lower_bound(now);
            while(iter != mp.end()){
                mp[now-1] += iter->first/now*iter->second;
                mp[(iter->first)%now] +=iter->second;
                mp.erase(iter ++);
            }
        }
        int sz = mp.size();
        auto iter = mp.begin();
        sum[sz+1] = 0;
        for(int i= 1;i <= sz;i ++){
            pos[i] = iter->first;
            sum[i] = iter->second;
            iter ++;
        }
        for(int i = sz;i >= 1;i --) sum[i] += sum[i+1];
        int ans= 0;
        int qs;
        cin >> qs;
        for(int i= 1;i <= qs;i ++){
            int now;
            scanf("%d",&now);
            int tmp = lower_bound(pos+1,pos+sz+1,now)-pos;
            ans = (ans+1LL*sum[tmp]*i)%mod;
        }
        cout << ans << endl;

    }

    return 0;
}