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]
相关推荐
03-16 18:26
广东工业大学 嵌入式工程师 点赞 评论 收藏
分享
讲原则的小黄鸭不愿吃...：有时候面试眼缘确实很重要，当然，飞驰人生2中张弛说的很对：我努力了无数次，但是我知道机会只会出现在其中一两次。你把每一次笔试面试都全力以赴，总有你运气发挥到位的时候 点赞 评论 收藏
分享