首页 > Harder Gcd Problem
开通博客写题解
头像 精神病科黄主任
发表于 2020-07-20 17:33:11
题意：给出1-n的数字，让选择m对数字，让gcd(a_i,b_i)>1，让m尽可能大，并且输出这m对对应的数字。 思路：整体的思路就是筛法+贪心。不过我代码写的比较复杂，比较low。。首先就是筛法，把n个数的质因子种类数，和最小质因数维护出来。cnt[i]表示i的质因子有多少种，mi[i]表示 展开全文
去ta的博客 赞 (6) 回复(0) 收起
头像 TitanZhang
发表于 2020-07-21 16:47:17
题目大意 给出一个集合的大小n，构造两个一样的集合A和B，分别包含{1,2,...,n}。 对两个集合中的不同数两两组合，每一对gcd(Api,Bqi)>1，求最多有多少对。 解题思路 思路一： 首先应该考虑有那些数不能参与匹配。显而易见1和大于n/2的素 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 Peterliang
发表于 2020-07-21 17:32:11
题目的意思，相对来说比B题更好懂一点，但需要思维却要比B题更高一点。题目：题意：从1-n里面选择最多的组合，使得每个组合的两个数的最大公因数不为1。输出组合的个数和这些组合的可能情况思路：贪心+STL+数论。枚举小于n/2的质因数，按从大到小的顺序进行枚举，首先，我们说说为什么要枚举质因数，我们发现 展开全文
去ta的博客 赞 (4) 回复(1) 收起
头像 Cur1ed
发表于 2020-07-21 00:26:44
H. Haeder Gcd Problem 题意 集合A和B都是{1,2,.....,n}的子集，A∩B≠∅。问A和B最多有多少对数GCD(Ap，Bq)>1。 题解 所有gcd>1的两个数肯定是倍数关系，最小肯定是本身和2倍。越大的数能和他匹配的就会越少，为了简单，从大的数往小的数匹配。 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 Lesning
发表于 2020-07-20 20:18:19
题意已经有很多大佬说过了，我用集合整了一个好理解但是慢的写法(毕竟2e5.....) 先求出list[x] 表示 x的最大质数因子是list[x],可以筛一波然后扔进集合，从大质数因子开始遍历。如果集合x大小是奇数(最大质因子是x的数字有奇数个)，那就把其中的偶数扔进集合2.最后把集合2判断完就行( 展开全文
去ta的博客 赞 (2) 回复(2) 收起
头像 一衍一
发表于 2020-07-20 20:39:01
题意:写出 的两个子集A,B,并且*两个子集的长度相等,且两个子集的交集为空,并且相对应位置的 *,然后第一行输出长度m,下来m行输出所构成的子集中的顺序题解:直接看样例1 2 3 4 5 6 7 8 9 10 11 12 13 14 157 145 153 69 122 48 10如果要gcd&g 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 11D_Beyonder
发表于 2020-08-19 00:04:18
题目描述   After solving the Basic Gcd Problem, ZYB gives you a more difficult one:  Given an integer , find two subset and of such that: and ; let a 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 zjnu_tjq
发表于 2020-07-27 20:04:46
链接：https://ac.nowcoder.com/acm/contest/5669/H来源：牛客网 题意： 给你一个1-n的数，让你将n个数分成两堆，且对应的两个数gcd不为1，也就是不互质 solution： 可以从最大的质数k开始往后构造，找出尽可能多的k的奇数倍，如果k的奇数倍的个数为奇数 展开全文
去ta的博客 赞 (1) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”