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]
相关推荐
不愿透露姓名的神秘牛友
07-25 17:59
爱睡觉的冰箱哥：填完自评就可以走了啊，八月初走没毛病
投递美团等公司10个岗位 点赞 评论 收藏
分享
07-23 15:14
重庆理工大学 机械结构工程师 点赞 评论 收藏
分享
点赞 评论 收藏
分享
06-03 16:55
广州工商学院 单片机 
点赞 评论 收藏
分享
腾讯一面2190人在聊