n<=1e6怎么做

B3957 [GESP202403 三级] 完全平方数

liruizhou_lihui @ 2024-12-06 17:53:30

rt.有没有 n \log n 做法。

能不能预处理出范围内完全平方数，然后就变成 A+B数对

by light_searcher @ 2024-12-06 17:58:32

可以吧，但可能要卡常

by light_searcher @ 2024-12-06 18:00:01

枚举完全平方数加扫一遍是不是就行

by DYF2765491381672943 @ 2024-12-06 18:08:10

@light_searcher 不是很理解，枚举完全平方数不是 n\sqrt n 的吗？

by zhangzirui66 @ 2024-12-06 18:33:07

@DYF2765491381672943 \sqrt{n} 吧

by DYF2765491381672943 @ 2024-12-06 18:36:33

@zhangzirui66 我的想法是枚举了每个数还得搜一遍有多少种和为这个数的 i 和 j ，所以我算出来是 n \sqrt n

by hesiwei2027 @ 2024-12-06 18:36:39

红名dalao做入门？

by zhangzirui66 @ 2024-12-06 18:37:51

@DYF2765491381672943 要先预处理吧

by zhangzirui66 @ 2024-12-06 18:38:12

综合就 O(n) 或 O(n\log n)

by light_searcher @ 2024-12-06 18:44:15

@DYF2765491381672943 值域没那么大

|