腾讯笔试 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-21 14:03
门头沟学院 C++
点赞 评论 收藏
分享
11-19 17:20
长春理工大学 供应链专员
点赞 评论 收藏
分享
头像
11-09 17:30
门头沟学院 Java
抽象华为
TYUT太摆金星：我也是，好几个华为的社招找我了
点赞 评论 收藏
分享
11-19 23:36
未填写教育信息 Java
家人们，谁懂啊！免费实习
都还没面试就给我下了判决书
废铁汽车人：秋招真是牛鬼蛇神齐聚一堂
点赞 评论 收藏
分享
11-23 09:59
华为_算法工程师
在华为不搞996，我们搞什么？
在华为不搞996，我们搞什么？本文原创首发于公众号：来知晓。楔子读者盆友们晚上好，欢迎来到来知晓。今晚咱们揭秘下之前在推文：华为加班有多“狠”？中埋的那个坑：一个让我每天灵感爆发，神清气爽的一个秘诀。正式开始之前，先问几个问题：你是否总感觉精力不够用？你是否总感觉想什么都抓，可什么都抓不住？你是否会偶尔觉得青春散场大学毕业后，从此生活缺乏许多乐趣？你是否总觉得自己总克服不了拖延，21年就快翻篇，却依然岁岁年年flag相似？如果你的回答大多是：Yes，你可能不是抑郁了，也许是跟我一样，并非缺乏上进的心，只是找不到使劲的力，把大部分精力都耗散在没有焦点的事物上了。下面我将分享个人历时两个多月亲身实...
凯文格拉汉姆：转人工
点赞 评论 收藏
分享
1 3 评论
分享

全站热榜

正在热议
# 25届秋招总结 #
280934次浏览 2438人参与
# 如果实习可以转正，你会不会放弃秋招 #
206209次浏览 2808人参与
# 北方华创开奖 #
24685次浏览 263人参与
# 地方国企笔面经互助 #
3320次浏览 7人参与
# 学历or实习经历，哪个更重要 #
47738次浏览 369人参与
# 选完offer后，你后悔学本专业吗 #
16996次浏览 120人参与
# 如何一边实习一边秋招 #
989427次浏览 12623人参与
# 软开人，秋招你打算投哪些公司呢 #
41786次浏览 534人参与
# 数据人的面试交流地 #
436525次浏览 7814人参与
# 0offer是寒冬太冷还是我太菜 #
893519次浏览 7966人参与
# 得物求职进展汇总 #
65035次浏览 674人参与
# 求职遇到的搞笑事件 #
69131次浏览 572人参与
# 你觉得专业和学校哪个对薪资影响最大 #
29014次浏览 215人参与
# 查收我的offer竞争力报告 #
21436次浏览 263人参与
# 你最想要的公司福利是？ #
43667次浏览 162人参与
# 没有实习经历，还有机会进大厂吗 #
809423次浏览 13890人参与
# 来聊聊机械薪资天花板是哪家 #
67591次浏览 460人参与
# 当你面对裁员会如何？ #
26562次浏览 156人参与
# 一觉醒来，我觉醒了超级打工人系统 #
3688次浏览 38人参与
# 应届生被毁约被毁意向了怎么办 #
28896次浏览 247人参与
# 面试体验感最好的是哪家？ #
84244次浏览 822人参与
牛客网
牛客企业服务