TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

95.6% (43/45)

Submission's AC Ratio

39.5% (68/172)

Tags

Description

蝴蝶在路旁玩壞一台販賣機,它一次只能投一枚硬幣(故障?)。重點是:投進一枚 $x$ 元的硬幣,然後按退幣鈕,居然會吐出一枚價值 $f(x)$ 的硬幣耶!更神秘的是,天才蝴蝶已經發現 $f(x) = x + (x-b_1) (x-b_2) (x-b_3) \cdots (x-b_m)$。
現在蝴蝶手上有 $n$ 枚硬幣,分別是 $a_1 \cdots a_n$,請問蝴蝶投進去會賺的硬幣有幾枚?

Input Format

第一行是兩個正整數 $n, m$
第二行是 $n$ 個數字 $a_1 \cdots a_n$
第三行是 $m$ 個數字 $b_1 \cdots b_m$
對於所有測資:

  • $1 \leq n, m \leq 10 ^ 5$
  • $-2 ^ {30} \leq a_i, b_i \leq 2 ^ {30}$

Output Format

請輸出一個整數,代表有幾枚會賺呢?

Sample Input

2 2
2 2
2 2

Sample Output

0

Hints

Problem Source

原TIOJ1614 / problem setter: 乃牛

2021.02.09 Update: Added $\LaTeX$ by FHVirus

Subtasks

No. Testdata Range Score
1 0 20
2 1 20
3 2 20
4 3 20
5 4 20

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 2
2 1000 65536 262144 3
3 1000 65536 262144 4
4 1000 65536 262144 5