2023-03-26 22:29 西安电子科技大学 C++ 发布于陕西
关注
腾讯笔试 3-26
第五题，求所有公约数为k的子集个数。
求问各位大佬怎么做的。
求问各位大佬怎么做的。
全部评论
神崎兰子
偶像大师灰姑娘女孩 后端
先处理掉不是k的倍数的元素，剩下的先默认除以k，然后容斥一下，发现加的部分和减的部分莫比乌斯函数有关系，筛一下就行了
未知多少 楼主
楼主 西安电子科技大学 C++
我的思路是，求所有是k的倍数的个数，然后看有没有不是k倍数的数，结果排列组合的时候要用到一个简单的二项式定理。
fw伊泽
北京理工大学 golang
莫比乌斯反演或者容斥+莫比乌斯函数
巴扎嘿_
平顶山学院 Java
dp就行吧
f[i] 表示最大公约数为i的方案数
容量只需要枚举k的倍数就行(否则会超时)
状态转移f[__gcd(a[i], j)] += f[j]
相关推荐
投递京东等公司10个岗位 
Bolee：一般般吧，看看我的
查看图片 点赞 评论 收藏
分享