# B

# 题意

对于给定方程 (d + x) % q[t] == r[t] ，已知 $d,q_t,r_t$，求 $d+x$

# 题解

方程等价于： d + x = k * q[t] + r[t]
x = k * q[t] + r[t] - d
因为 $x \ge 0$，所以可以得到

$$k · q[t] + r[t] - d \ge 0$$

等价于

$$k \ge \frac{d - r[t]}{q[t]}m,minn(k) = \lceil{\frac{d - r[t]}{q[t]}}\rceil$$

可以写成

$$k = \frac{d-r[t]+q[t]-1}{q[t]}$$

总结有 $\lceil{\frac{a}{b}}\rceil$ = $\frac{a+b-1}b$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

q = [0 for _ in range(110)]
r = [0 for _ in range(110)]

n = int(input())
for i in range(1, n + 1):
    (q[i], r[i]) = list(map(int, input().split()))

z = int(input())
for i in range(z):
    (t, d) = list(map(int, input().split()))

    k = (d - r[t] + q[t] - 1) // q[t]  # 等价于向上取整
    # 计算 x
    x = k * q[t] + r[t] - d

    print(d + x)

# E

# 题意

给你一个由 $N$ 个非负整数组成的序列 $A = (A_1, A_2, ..., A_N)$ 和一个正整数 $M$ 。
求下列数值：

$$\sum_{1 \leq l \leq r \leq N} \left( \left(\sum_{l \leq i \leq r} A_i\right) \mathbin{\mathrm{mod}} M \right)$$

# 题解

设 $s_i$ 表示 $(\sum\limits_{j=1}^{i}{A_j})~mod~M$ 的值，那么原式可以转化成： $\sum\limits_{1 \le l \le r \le n} (s_r - s_{l-1})$
展开有：$\sum\limits_{1 \le i \le n}\sum\limits_{0 \le j \le i - 1} (s_i - s_{j-1})$
整理可得：$\sum\limits_{1 \le i \le n}(i * s_i - \sum\limits_{0 \le j \le i - 1}s_j)$
如果直接减，那么如果 $s_j > s_i$ 的话便会减出负数来，这个时候要加上一个 $m$
用树状数组维护对于每个 $i$ 有多少个 $s_j > s_i$，然后继续加上这么多 $m$ 就行

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

int n, m, sum[N], ans, res, c[N];

int lowbit(int x) {
    return x & -x;
}

void add(int x, int k) {
    while (x <= m)
        c[x] += k, x += lowbit(x);
}

int getSum(int x) {
    int ans = 0;
    while (x > 0)
        ans += c[x], x -= lowbit(x);
    return ans;
}

void solve () {
    cin >> n >> m;
    for (int i = 1, x; i <= n; i++) {
        cin >> x;
        sum[i] = (sum[i - 1] + x) % m;
    }

    for (int i = 1; i <= n; i++) {
        ans += i * sum[i] - res + (getSum(m) - getSum(sum[i] + 1)) * m;
        res += sum[i];
        add(sum[i] + 1, 1);
    }

    cout << ans << endl;
}