首页 > 代码库 > [HDU5902]GCD is Funny(xjb搞)
[HDU5902]GCD is Funny(xjb搞)
题意:n个数每次选三个数删除,取其中两个数将gcd放回去两次,问最后剩的数可能是多少
分析:考虑最优情况:
先拿出三个数,留下两个x,x
再来一个y,(x,x,y)我们可以删去一个x,留下两个gcd(x,y),这两个gcd(x,y)等价于刚才的两个x,x
也就是每次操作我们都可以有一个额外的数让我们删去,并不断扩充gcd
于是答案就是所有子集的gcd
但第一次我们必定删去一个数,它没法加入gcd操作中,所有n个子集的gcd不能作为最终结果
即答案就是2<=size<n的子集的gcd
可以先跑出两两gcd,然后再枚举子集的大小,不断更新gcd
[HDU5902]GCD is Funny(xjb搞)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。