P4337.【数学4】潜在同好
本题为2025年8月24日小红书机考原题
小红书机考的介绍点击这里
题目内容
在小红书平台的社交推荐项目中，产品团队希望基于用户的日常行为习惯分数，挖掘潜在的“同好”关系。
系统简化如下，数据库中有 n 个用户的日常行为习惯分数，第 i 个用户的分数使用 ai 表示。记第 i 个用户和第 j 个用户构成“同好”关系，当且仅当 ai 能被 aj 整除，或者 aj 能被 ai 整除。
接下来将进行 m 次查询，每次给定一个额外的用户行为分数 x ，请统计在数据库中，有多少不同的人能与这个人构成“同好”关系。
输入描述
第一行输入两个整数 n,m(1≤n,m≤5•105) ,表示数据库中用户数量、查询次数。
第二行输入 n 个整数 a1,a2,…,an(1≤ai≤5•105) ,表示数据库中的用户日常行为习惯分数。
接下来m行，每行输入一个整数 x(1≤x≤5•105) ,表示一个额外的用户行为习惯分数。
输出描述
对于每次查询，新起一行，输出一个整数，表示数据库中能与 x 构成“同好”关系的用户数量。
样例1
输入
5 3
1 2 2 5 6
4
2
1
输出
3
4
5
开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写
