思路

• 设 $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$ 整除的人数）。

• 则每次查询答案为：

  • 

题目内容

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

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