培玉 · 一试

专题地图 › 数论

2017 年湖南预赛 · 第 4 题

F1选择题数论

对任意正整数 与 (),用 表示不超过 且与 互质的正整数的个数(其中 表示不超过 的最大整数),则

  1. (A)

  2. (B)

  3. (C)

  4. (D)

作答

解析

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

需准确读取定义中的取整上界,再用100的素因子筛出互素数,核一与闭端点。

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

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

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