腾讯笔试 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 北京

相关推荐

孤寡孤寡的牛牛很热情:为什么我2本9硕投了很多,都是简历或者挂,难道那个恶心人的测评真的得认真做吗
点赞 评论 收藏
分享
hso_:哈哈哈哈哈哈我没offer一样在同一道题开喷了
投递深圳同为数码等公司10个岗位
点赞 评论 收藏
分享
评论
1
3
分享
牛客网
牛客企业服务