腾讯笔试 3-26

第五题，求所有公约数为k的子集个数。
求问各位大佬怎么做的。
全部评论
先处理掉不是k的倍数的元素，剩下的先默认除以k，然后容斥一下，发现加的部分和减的部分莫比乌斯函数有关系，筛一下就行了
3 回复 分享
发布于 2023-03-26 22:30 天津
我的思路是，求所有是k的倍数的个数，然后看有没有不是k倍数的数，结果排列组合的时候要用到一个简单的二项式定理。
1 回复 分享
发布于 2023-03-26 22:32 陕西
dp就行吧 f[i] 表示最大公约数为i的方案数 容量只需要枚举k的倍数就行(否则会超时) 状态转移f[__gcd(a[i], j)] += f[j]
点赞 回复 分享
发布于 2023-03-26 22:41 河南
莫比乌斯反演或者容斥+莫比乌斯函数
点赞 回复 分享
发布于 2023-03-28 09:57 北京

相关推荐

11-18 00:45
大连理工大学 机械设计/制造
点赞 评论 收藏
分享
11-22 17:55
沈阳工业大学 机械其它
点赞 评论 收藏
分享
11-03 14:38
重庆大学 Java
Offer太多了不知道怎么选啊
AAA求offer教程：我手都抬起来了又揣裤兜了
点赞 评论 收藏
分享
11-19 15:23
菜鸟集团_安全工程师(准入职员工)
菜鸟内推菜鸟面经
面试的过程中感慨了平台的重要性，之前做的东西都太表层了，有时候可能一个平台才可能会有这些实际的应用场景二轮技术面（面试官职位应该比较高，并不会问八股文，全程问项目，和非常底层的知识，和一些整体的思考，奈何自己水平不够，我会附上我当时的回答，简单的记录一下给各位牛友参考）1. 自我介绍 我喜欢简单的自我介绍，就说了一下自己毕业时间，掌握哪些技术，公司参与过公司内部使用的系统，也参与过面向用户app的服务端开发工作，然后说了本次的求职岗位2. 独立负责这个项目的时候，你为什么要使用spring boot架构？ 回答侧重点：理论上市面上最成熟的架构，本身支持自动配置减少自动配置的工作，可...
点赞 评论 收藏
分享
1 3 评论
分享

全站热榜

正在热议
# 25届秋招总结 #
286171次浏览 2515人参与
# 学历or实习经历，哪个更重要 #
48774次浏览 376人参与
# 阿里云管培生offer #
3876次浏览 85人参与
# 地方国企笔面经互助 #
3436次浏览 7人参与
# 美团求职进展汇总 #
1322941次浏览 12415人参与
# 选完offer后，你后悔学本专业吗 #
18224次浏览 130人参与
# 百度开奖 #
149289次浏览 902人参与
# 如何一边实习一边秋招 #
989983次浏览 12628人参与
# 腾讯求职进展汇总 #
194702次浏览 1632人参与
# 银行笔面经互助 #
82019次浏览 872人参与
# 提前批简历挂麻了怎么办 #
145952次浏览 1942人参与
# 0offer是寒冬太冷还是我太菜 #
895175次浏览 7983人参与
# 海康威视求职进展汇总 #
397796次浏览 3403人参与
# 机械人，你在招聘流程中的企业有哪些？ #
17750次浏览 186人参与
# 得物求职进展汇总 #
65467次浏览 676人参与
# 没有实习经历，还有机会进大厂吗 #
810415次浏览 13913人参与
# 你们公司几号发工资 #
10652次浏览 99人参与
# 网申一定要掌握的小技巧 #
5235次浏览 52人参与
# 学历对求职的影响 #
343293次浏览 3138人参与
# 听到哪句话就代表面试稳了or挂了？ #
93693次浏览 785人参与
# 机械人与华为的爱恨情仇 #
72081次浏览 664人参与
# 查收我的offer竞争力报告 #
21757次浏览 267人参与
牛客网
牛客企业服务