Problem J2: Count the Divisors / 统计因数个数

任务总览表

题目描述

给定两个正整数 A 和 B，请计算在区间 [1, B] 内，有多少个整数是 A 的因数。换句话说，统计满足 A 整除 x（即 A | x）的整数 x 的个数，其中 1 <= x <= B。

输入格式

输入包含两个正整数 A 和 B，保证 1 <= A, B <= 1000000。

输出格式

输出一个整数，表示在区间 [1, B] 内 A 的因数的个数。

样例输入 1

3 10

样例输出 1

3

​解释​：在区间 [1, 10] 内，能被 3 整除的数有 3, 6, 9，共 3 个。

样例输入 2

4 20

样例输出 2

5

​解释​：在区间 [1, 20] 内，能被 4 整除的数有 4, 8, 12, 16, 20，共 5 个。

提示

• A 的因数指的是可以被 A 整除的数，即满足 A | x 的所有 x。

• 计算从 1 到 B 中有多少个数是 A 的倍数，可以使用公式：

  count = B / A
  

  这可以在 O(1) 时间内计算得出。

题目分析

​目标​：求区间 [1, B] 内能被 A 整除的数的个数。 ​思路​：

• 一个数 x 是 A 的因数当且仅当 x 是 A 的倍数，即 A | x。
• 在 [1, B] 内，A 的倍数是 A, 2A, 3A, ... , kA，其中 k = B / A。
• 直接计算 B / A 即可得到答案，时间复杂度为 O(1)。

时间复杂度分析

• 直接使用整除运算 B // A，只需要 O(1) 的时间。
• 由于 A, B 最大为 1000000，该解法能在 1 秒内高效运行。

结论

• 该问题可以用数学方法高效求解，无需遍历 1 到 B 的所有数。
• 关键在于理解“整除”的定义，以及利用整除运算符 / 快速计算答案。