题目内容

在小红书平台做社交推荐时，产品组想凭用户平日行为习惯得分，找出可能的“同好”联系。 系统被简化成下面这样：库里存放 $p$ 位用户的平日行为习惯得分，第 $k$ 位用户的得分记成 $b_k$ 。称第 $k$ 位用户与第 $t$ 位用户形成“同好”联系，充要条件是 $b_k$ 可以被 $b_t$ 整除，或者 $b_t$ 可以被 $b_k$ 整除。

后面会有 $q$ 次询问，每次再给出一个习惯得分 $y$ ，请统计库里有几位互不相同的人能跟这个人形成“同好”联系。

输入描述

首行读入两个整数 $p,q(1\le p,q\le 5\cdot 10^5)$ ,用来标明库里的用户人数、询问次数。

次行读入 $p$ 个整数 $b_1,b_2,\ldots,b_p(1\le b_k\le 5\cdot 10^5)$ ,用来标明库里各位用户的平日行为习惯得分。

随后 $q$ 行，每行读入一个整数 $y(1\le y\le 5\cdot 10^5)$ ,用来标明库外这位访客的习惯得分。

输出描述

每一次询问独占一行，打印一个整数，用来标明库里能跟 $y$ 形成“同好”联系的用户人数。

样例1

输入

6 4
3 6 9 4 8 12
6
4
8
1

输出

3
3
2
6

开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写