首页 > Product of GCDs
开通博客写题解
头像 nagisa_菜鸡
发表于 2021-07-20 01:54:58
题目：https://ac.nowcoder.com/acm/contest/11253/J大意为给一个数组a，求数组a中所有大小为k的子集的gcd的乘积。 根据惯例，估计是转化为枚举gcd后统计贡献。对于每个i，我们需要求有几个子集的gcd为i，考虑组合数为，num为数组中i的倍数的个数，但这样统 展开全文
去ta的博客 赞 (4) 回复(3) 收起
头像 19-大数据一班-杨文冠
发表于 2021-07-22 10:59:20
思路：在集合中任选个数组成一个新集合，求所有新集合的乘积，因为比较小，很容易想到(总数不容易求，常见的套路就是求每个数的贡献)枚举假设表示的新集合的个数，表示(是的倍数)的新集合的个数，表示因子包含的数的个数，的贡献就是。那么，且如果要计算，那么y由上面的定义可以确定的是中已经计算过了，那么可以考虑 展开全文
去ta的博客 赞 (4) 回复(1) 收起
头像 KeHe
发表于 2021-07-20 01:03:23
考虑直接枚举 gcd⁡=p\gcd=pgcd=p ，枚举倍数统计出 fp=∑[p∣ xi]f_p=\displaystyle\sum[p\mid x_i]fp​=∑[p∣ xi​] ，那么 p∣gcd⁡p\mid\gcd 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 11D_Beyonder
发表于 2021-09-02 21:01:16
题目大意 给出多重数集 ，求其所有大小为 的子集的 之积。共 组数据，要求答案 输出。 不保证 中所有数各不相同，不保证 为质数。。 事后交题时感觉 。 思路 枚举所有可能出现的 ，设 的长度为 的子集个数为 ，那么最终答案 {%raw%}{%endraw%}。我们的任务是求出每 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”