培玉 · 一试

专题地图 › 数论

2023 年中科大少年班初试 · 第 5 题

F3解答题数论

将正整数去除完全平方数后由小到大排成一排,记作。例如。求证:对任意正整数,都有

作答

这是解答题,请在纸上写出完整过程。写完后对照解答给自己评分。

解析

为什么评为 F3(会透露解法方向)

须独立选择按输出a_n而非输入n定位平方段,再用整数性收紧到半单位误差;数论本期不用。

用到的方法(会透露解法方向)

核心工具:按整数阈值分层,累计计数

专题卡:分块、容斥与累计计数