ZOJ 3940 Modulo Query

Modulo Query

Time Limit: 2 Seconds      

Memory Limit: 65536 KB

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

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.

Author: 

LIN, Xi

Source: The 13th Zhejiang Provincial Collegiate Programming Contest

#include<queue>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int mod = 1e9 + 7;
const int maxn = 4e5 + 10;
int T, q, n, m, x, sum[maxn], b[maxn], ans, sz;

struct point
{
  int x, y;
  point(int x = 0, int y = 0) :x(x), y(y) {}
  bool operator<(const point&a)const
  {
    return x < a.x;
  }
}a[maxn];

int main()
{
  scanf("%d", &T);
  while (T--)
  {
    scanf("%d%d", &n, &m);
    priority_queue<point> p;
    p.push(point(m, 1));
    while (n--)
    {
      scanf("%d", &x);
      while (p.top().x >= x)
      {
        point q = p.top();  p.pop();
        while (!p.empty() && p.top().x == q.x) q.y += p.top().y, p.pop();
        p.push(point(x - 1, (q.x + 1) / x*q.y));
        if ((q.x + 1) % x)p.push(point(q.x%x, q.y));
      }
    }
    sz = 1; ans = 0;
    while (!p.empty())
    {
      point q = p.top();  p.pop();
      while (!p.empty() && p.top().x == q.x) q.y += p.top().y, p.pop();
      a[sz++] = q;
    }
    sort(a + 1, a + sz);
    for (int i = 1; i < sz; i++)
    {
      sum[i] = sum[i - 1] + a[i].y;
      b[i] = a[i].x;
    }
    scanf("%d", &q);
    for (int i = 1; i <= q; i++)
    {
      scanf("%d", &x);
      int k = lower_bound(b + 1, b + sz, x) - b;
      (ans += (LL)(sum[sz - 1] - sum[k - 1])*i%mod) %= mod;
    }
    printf("%d\n", ans);
  }
  return 0;
}