Problem : Count Coprime Numbers / 统计互质数个数

任务总览表

题目描述

给定一个正整数 A，请计算在区间 [1, A] 内，有多少个整数与 A ​互质​。换句话说，统计满足 gcd(x, A) = 1 的整数 x 的个数，其中 1 <= x <= A。

输入格式

输入包含一个正整数 A，保证 1 <= A <= 1000000。

输出格式

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

样例输入 1

10

样例输出 1

4

​解释​：在区间 [1, 10] 内，与 10 互质的数有 1, 3, 7, 9，共 4 个。

样例输入 2

12

样例输出 2

4

​解释​：在区间 [1, 12] 内，与 12 互质的数有 1, 5, 7, 11，共 4 个。

提示

• 两个数 x 和 A​互质​，意味着它们的最大公约数 gcd(x, A) = 1。

• 计算 1 到 A 之间与 A 互质的数的个数，等价于计算 ​**欧拉函数 φ(A)**​，即：

  φ(A) = A * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pk)
  

  其中 p1, p2, ..., pk 是 A 的所有不同质因数。

• 该值可以在 O(sqrt(A)) 时间内计算。

题目分析

​目标​：求区间 [1, A] 内，与 A 互质的数的个数。 ​思路​：

• 利用欧拉函数 φ(A) 计算与 A 互质的整数个数。
• 先分解 A 的所有不同质因数，再使用公式计算 φ(A)。
• 时间复杂度为 O(sqrt(A))，可以高效处理 A <= 1000000 的情况。

时间复杂度分析

• 通过 O(sqrt(A)) 的方法计算欧拉函数 φ(A)，可以快速得到答案。
• 由于 A 最大为 1000000，该方法能在 1 秒内高效运行。

结论

• 该问题利用了数论中的 互质性 概念，核心在于计算欧拉函数 φ(A)。
• 通过数学推导，可以避免暴力遍历，优化计算复杂度至 O(sqrt(A))。