会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（小红书机考编程题库），可解锁完整内容。

购买题库开通会员

设 $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$ 枚古老的魔力徽章，每枚徽章上都铭刻着一个魔力数字 $a_i$ 。人们发现，两枚徽章之间会产生共鸣，当且仅当一个魔力数字能被另一个整除。

学院计划进行 $m$ 次新徽章测试。每次测试会提供一枚新徽章的魔力数字 $x$ ，请你快速统计陈列室已有的徽章中，有多少枚会与这枚新徽章产生共鸣。

约束： $n$ 和 $m$ 均不超过 $5 \times 10^5$ ，所有魔力数字均为不超过 $5 \times 10^5$ 的正整数。

输入描述

第一行包含两个整数 $n$ 和 $m$ $(1 \le n, m \le 5 \times 10^5)$ ，分别表示现有徽章数量和测试次数。

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

选择提交后点击「开始AI分析」