1 条题解
-
0黄天泽 (huangtianze) LV 7 @ 2024-7-31 22:35:02
这道题就是一道纯暴力。。。
我居然 WA 了前置知识: 表示两个数不互质。
首先,分析一下数据范围, 的情况下,两层循环枚举 和 , 的平方可以过。
现在,再来看看怎么将数组重排才是最优解。思考一下:什么情况下 ,但 却会大于 呢?现在假设 是偶数, 是奇数,是不是正好满足上面的性质?所以 是偶数的情况下,无论 变成什么,乘二后都会变成偶数,两个偶数的最大公因数肯定会大于 ,再来分析一下样例:
4 3 6 5 3
如果把奇数和偶数分开,把偶数放在前面,奇数放在后面,样例就变成了
6 5 3 3
,然后再两层 for 循环枚举 和 ,最后符合条件的就剩下了 、、、,正好是 对。最后,总结一下此题思路:将数组中的所有偶数放在前面,奇数放后面,然后循环暴力枚举符合条件的数量就可以 AC。
AC 代码很简单,学过入门的都会,只提供判断 gcd 函数的代码(辗转相除法)
int gcd(int a,int b){ if(b==0) return a; return gcd(b,a%b); }
- 1
信息
- ID
- 2348
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 7
- 标签
- 递交数
- 74
- 已通过
- 19
- 上传者