「给 TLE 最后三个点的一些建议」

给 TLE 最后三个点的一些建议

被骇客银狼阻止的越权访问保存失败

给 TLE 最后三个点的一些建议

my_dream666楼主2025/7/26 11:44

这题的时间瓶颈其实在于求 gcd,因为这题单个 gcd 的时间复杂度（辗转相除法）是 $\log_{2}{n}$ ,约为 24，那么这一步骤的时间的就是 100 $\times 500$ $\times 500$ $\times 24$ = 6 $\times 10^8$ ，再加上我们的匈牙利，最后三个点就会超时（~~虽然按理来说单是匈牙利就会超时）~~，但是实际上总是跑不满。
那么我们就可以对 gcd 进行优化，我们用埃氏筛预处理处每个数的最小质因数，再用 vector 存输入的每个数的所有质因数，再两两枚举，根据计算可知， $10^7$ 中含质因数最多的数所含的质因数的个数也只是8个，那么这一步骤的时间就是 100 $\times 500$ $\times 500$ $\times 8$ $\times 8$ = 1.6 $\times 10^9$ ，这时候你么肯定会说这不必上面的 gcd 要差吗，实则不然。
我们可以在找到相同质因数的时候返回，这样实际上的最大枚举次数只是 4 $\times 4$ ，并不是 64 ，所以实际上它的时间只是100 $\times 500$ $\times 500$ $\times 4$ $\times 4$ = 4 $\times 10^8$ ，加上我们预处理的，你可以用埃氏筛，也可以用欧拉筛，时间差不了太多，接近与线性。
总的来说，这题只用对判断是否有相同质因数进行优化就行了。（虽然好像只优化了一点，但实际上跑出来的时间总共快了 1.6s )

2025/7/26 11:44