思路

• 设 $U=5\times 10^5$，用数组 freq[v] 统计每个分数出现次数。

• 预处理：

  • $divCnt[x] = \sum_{d\mid x}\text{freq}[d]$（数据库中所有能整除 $x$ 的人数）。
  • $mulCnt[x] = \sum_{k\ge 1}\text{freq}[k\cdot x]$（数据库中所有被 $x$ 整除的人数）。

• 则每次查询答案为：

本题为2025年8月24日小红书机考原题

小红书机考的介绍点击这里

题目内容

在小红书平台的社交推荐项目中，产品团队希望基于用户的日常行为习惯分数，挖掘潜在的“同好”关系。 系统简化如下，数据库中有 $n$ 个用户的日常行为习惯分数，第 $i$ 个用户的分数使用 $a_i$ 表示。记第 $i$ 个用户和第 $j$ 个用户构成“同好”关系，当且仅当 $a_i$ 能被 $a_j$ 整除，或者 $a_j$ 能被 $a_i$ 整除。

接下来将进行 $m$ 次查询，每次给定一个额外的用户行为分数 $x$ ，请统计在数据库中，有多少不同的人能与这个人构成“同好”关系。

输入描述

第一行输入两个整数 $n,m(1≤n,m≤5•10^5)$ ,表示数据库中用户数量、查询次数。

第二行输入 $n$ 个整数 $a_1,a_2,…,a_n(1≤a_i≤5•10^5)$ ,表示数据库中的用户日常行为习惯分数。

接下来m行，每行输入一个整数 $x(1≤x≤5•10^5)$ ,表示一个额外的用户行为习惯分数。

输出描述

对于每次查询，新起一行，输出一个整数，表示数据库中能与 $x$ 构成“同好”关系的用户数量。

样例1

输入

5 3
1 2 2 5 6
4
2
1

输出

3
4
5