• 周四. 12 月 12th, 2024

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

Codeforces 人类智慧题目大赏

admin

11 月 28, 2021

提示:有些题目可以有更简单的办法做掉,但是这里仅提供一些奇怪的思路。该文章会定期更新。

类型一 人力算实际取值题

1. CF235A LCM Challenge

题意:

  • 找到三个数 $a,b,c$ 满足 $1 le a,b,c le n$,使得 $lcm(a,b,c)$ 最大。$n le 10^6$。

题解:

  • 对于 $n$ 较小时直接暴力。
  • 剩下的情况我们做一个大胆的猜想:$1 le x,y,z le n$ 最大的 $3$ 个不同质数 $x,y,z$,均不小于 $n-200$。
  • 然后题做完打个表发现 $n le 10^6$ 范围内均是正确的。
  • $O(200^3 log n)$ 暴力枚举 + 求 LCM,从 $min(1,(n-200)) sim n$ 中选出 $3$ 个数,找出最大 LCM 即可。
  • 官方题解解法差不多,但是把范围缩得更小,为 $[min(1,n-50),n]$。

类似思路题目:

发表回复