G - Dot Product Query
Flavor
2.5
s
1024
MB
700
点
問題文
長さ $N$ の整数列 $A=(A_1, \cdots, A_N),\space B=(B_1, \cdots, B_N)$ が与えられます。
$Q$ 個のクエリが与えられます、$i$ 番目のクエリでは、次の問いに答えてください。
- 正整数 $C_i$ が与えられます。数列 $B$ の 0 個以上の要素を適当な整数に変更することで、$\sum_{1 \leq j \leq N} A_j B_j = C_i$ を満たすことができるか判定し、可能な場合は変更する要素の個数の最小値、不可能な場合は $-1$ を出力してください。
制約
- 入力は全て整数
- $1 \leq N \leq 2\times 10^5$
- $1 \leq A_i, B_i \leq 2\times 10^5$
- $1 \leq Q \leq 2\times 10^5$
- $1 \leq C_i \leq 2\times 10^5$
入力
入力は以下の形式で標準入力から与えられます。
$N$
$A_1\space A_2 \cdots \space A_N$
$B_1\space B_2 \cdots \space B_N$
$Q$
$C_1$
$\vdots$
$C_Q$
出力
$Q$ 行出力してください。$i$ 行目には 、$i$ 番目のクエリの答えを出力してください。
入力例 1
2
4 6
1 1
3
10
12
15
出力例 1
0
2
-1
1 番目のクエリでは、最初から
$4 \times 1 + 6 \times 1 = 10$
2 番目のクエリでは、例えば、$B=(0, 2)$ と変化させることで達成できます。$B$ の要素を 1 個だけ変化させて 12 にする方法はないため、$2$ を出力します。
3 番目のクエリでは、どのように $B$ の要素の値を変えても 15 にする方法はないため、$-1$ を出力します。
入力例 2
4
6808 13432 21608 54464
36547 38713 81367 192146
5
17
176
1760
17608
176080
出力例 2
-1
2
3
3
1