Problem:

F: MOD Rush

問題

長さ N の正の整数列 A と、長さ M の正の整数列 B が与えられます。

すべての (i, j) (1 \leq i \leq N, 1 \leq j \leq M) について、A_i を B_j で割ったあまりを求め、それらの和を出力してください。

入力形式

N M
A_1 A_2 ... A_N
B_1 B_2 ... B_M

制約

 1 \leq N, M \leq 2 \times 10^5

 1 \leq A_i, B_i \leq 2 \times 10^5

 入力はすべて整数で与えられる

出力形式

答えを 1 行に出力してください。最後に改行してください。

入力例 1

3 3
5 1 6
2 3 4

出力例 1

9

 数列 A の 1 番目の要素を、数列 B の各要素で割ったあまりを考えます。5 を 2 で割るとあまりは 1、3 で割るとあまりは 2、4 で割るとあまりは 1 です。

 同様に 2 番目の要素についても考えると、あまりはそれぞれ 1, 1, 1 です。

 3 番目の要素についても考えると、あまりはそれぞれ 0, 0, 2 です。

 あまりを合計すると 1 + 2 + 1 + 1 + 1 + 1 + 0 + 0 + 2 = 9 となるので、9 を出力します。

入力例 2

2 4
2 7
3 3 4 4

出力例 2

16

 数列内には同じ値が複数含まれていることがありますが、それぞれの要素に対してあまりを計算して和を求めます。

入力例 3

3 1
12 15 21
3

出力例 3

0



Sample input:
3 3
5 1 6
2 3 4


Sample output:
9

Submission status: Accepted

Solution code:
from collections import Counter
from itertools import accumulate
N, M = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

K = max(A)
table = [0]*(K+1)

table[0] = M
for b, v in Counter(B).items():
    for j in range(b, K+1, b):
        table[j] -= b*v
    for j in range(b+1, K+1, b):
        table[j] += b*v
table = list(accumulate(table))
table[0] = 0
table = list(accumulate(table))

print(sum(table[a] for a in A))