腾讯笔试 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-27 18:28
中南大学 Java
点赞 评论 收藏
分享
11-22 00:38
南京大学 Java
点赞 评论 收藏
分享
11-21 04:35
电子科技大学 Java
还没约面问最低薪资😅
逆天公司，这种正常吗😅
努力学习的小绵羊：我反倒觉得这种挺好的，给不到我想要的就别浪费大家时间了
点赞 评论 收藏
分享
头像
11-11 19:29
华中科技大学 嵌入式软件工程师
以前真的是被华子打包带走啊 形势变太快了
joe2333：怀念以前大家拿华为当保底的日子
点赞 评论 收藏
分享
11-27 11:10
哈尔滨理工大学 算法工程师
点赞 评论 收藏
分享
评论
1
3
分享

全站热榜

正在热议
# 25届秋招总结 #
377164次浏览 3742人参与
# 如果再来一次，你还会选择这个工作吗？ #
101223次浏览 1021人参与
# 北方华创开奖 #
64579次浏览 503人参与
# 地方国企笔面经互助 #
6027次浏览 14人参与
# 简历被挂麻了，求建议 #
2525045次浏览 33457人参与
# 发工资后，你做的第一件事是什么 #
4674次浏览 19人参与
# 阿里云管培生offer #
46231次浏览 1377人参与
# ai智能作图 #
11211次浏览 181人参与
# 我的实习求职记录 #
6105378次浏览 83837人参与
# 如果你有一天可以担任公司的CEO，你会做哪三件事？ #
8822次浏览 180人参与
# 上班到公司第一件事做什么？ #
14579次浏览 164人参与
# 阿里求职进展汇总 #
71822次浏览 780人参与
# 如何写一份好简历 #
615901次浏览 8700人参与
# 听到哪句话就代表面试稳了or挂了？ #
96734次浏览 810人参与
# 还记得你第一次面试吗？ #
29627次浏览 416人参与
# 华为工作体验 #
109391次浏览 852人参与
# 面试体验感最好的是哪家？ #
91566次浏览 921人参与
# 网易求职进展汇总 #
38904次浏览 334人参与
# 如果有时光机，你最想去到哪个年纪？ #
27062次浏览 559人参与
# 腾讯求职进展汇总 #
205699次浏览 1687人参与
# 硬件兄弟们 甩出你的华为奖状 #
75808次浏览 615人参与
# 上班苦还是上学苦呢？ #
106756次浏览 865人参与
牛客网
牛客企业服务