频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
Ural 1091. Tmutarakan Exams (莫比乌斯反演)
2013-12-14 11:29:13         来源:JayYe的专栏  
收藏   我要投稿

题目链接: https://acm.timus.ru/problem.aspx?space=1&num=1091

题意:

从1~S个数字里选出K个数使得K个数的gcd > 1的选择情况数有多少种,注意的是,如果答案大于10000,输出10000即可。K<=S<=50

思路:

很简单的莫比乌斯反演水题,设F(x)为选出k个数的gcd为x的倍数的情况数,则反演函数f(x)即为选出k个数的gcd为x的情况数就可以了。

这题数据范围小,所以其实直接用容斥原理也可以做,莫比乌斯反演其实就是计算各个容斥系数。


点击复制链接 与好友分享!回本站首页
相关TAG标签 乌斯 莫比
上一篇:fzu 2107 Hua Rong Dao(回溯)
下一篇:fzu 2104 Floor problem(水题)
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站