1614 . 販賣機耶
TopCoder
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 1
2 2
2 2
2 2
2 2
2 2
Sample Output 1
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 |