1 条题解

  • 0
    @ 2024-7-31 22:35:02

    这道题就是一道纯暴力。。。我居然 WA 了

    前置知识:gcd(a,b)>1\gcd(a,b)>1 表示两个数不互质

    首先,分析一下数据范围,n2000n \leq 2000 的情况下,两层循环枚举 iijj20002000 的平方可以过。

    现在,再来看看怎么将数组重排才是最优解。思考一下:什么情况下 gcd(ai,aj)=1\gcd(a_i,a_j)=1 ,但gcd(ai,aj×2)\gcd(a_i,a_j\times2) 却会大于 11 呢?现在假设 aia_i 是偶数,aja_j 是奇数,是不是正好满足上面的性质?所以 aia_i 是偶数的情况下,无论 aja_j 变成什么,乘二后都会变成偶数,两个偶数的最大公因数肯定会大于 11,再来分析一下样例:

    4
    3 6 5 3
    

    如果把奇数和偶数分开,把偶数放在前面,奇数放在后面,样例就变成了6 5 3 3,然后再两层 for 循环枚举 iijj,最后符合条件的就剩下了 6,2×56,2\times 56,2×36,2\times 36,2×36,2\times 33,2×33,2\times 3,正好是 44 对。

    最后,总结一下此题思路:将数组中的所有偶数放在前面,奇数放后面,然后循环暴力枚举符合条件的数量就可以 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
    上传者