题目理解

题目要求我们计算一个正整数 n 的欧拉函数值 φ(n)，即小于 n 且与 n 互质的正整数的个数。两个数互质是指它们的最大公约数为1。例如：

• n = 7 时，小于7且与7互质的数为1, 2, 3, 4, 5, 6，共6个，所以 φ(7) = 6。
• n = 12 时，小于12且与12互质的数为1, 5, 7, 11，共4个，所以 φ(12) = 4。

解题思路

欧拉函数的计算基于 n 的质因数分解。具体步骤如下：

1. 质因数分解：将 n 分解为质因数的乘积。例如，12 = 2^2 * 3^1。
2. 应用欧拉函数公式：
   • 如果 n 是一个质数 p，则 φ(p) = p - 1。
   • 如果 n 可以分解为质因数的乘积 n = p1^k1 * p2^k2 * ... * pm^km，则欧拉函数值为： $ φ(n) = n \times \left(1 - \frac{1}{p1}\right) \times \left(1 - \frac{1}{p2}\right) \times \dots \times \left(1 - \frac{1}{pm}\right) $
   • 例如，12 = 2^2 * 3^1，所以： $ φ(12) = 12 \times \left(1 - \frac{1}{2}\right) \times \left(1 - \frac{1}{3}\right) = 12 \times \frac{1}{2} \times \frac{2}{3} = 4 $

标程

#include <functional>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <map>
#include <bitset>
#include <set>
#include <vector>

using namespace std;

const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
const double eps = 1e-15;
typedef long long LL;
typedef pair <int, int> PLL;

int getphi(int n) {
    int ans = n;
    for (int i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            ans -= ans / i;
            while (n % i == 0) {
                n /= i;
            }
        }
    }
    if (n > 1) {
        ans -= ans / n;
    }
    return ans;
}

int main() {
    int n;
    while (~scanf("%d", &n), n) {
        printf("%d\n", getphi(n));
    }
    return 0;
}

代码解析

1. 函数 getphi：

   • 初始化 ans 为 n。
   • 遍历从2到 sqrt(n) 的所有整数 i，检查是否能整除 n：
     • 如果能整除，说明 i 是 n 的一个质因数，更新 ans 为 ans - ans / i，并将 n 中所有 i 的因子除尽。
   • 如果剩余的 n 大于1，说明 n 本身是一个质数，更新 ans 为 ans - ans / n。
   • 返回 ans 作为欧拉函数值。

2. 主函数 main：

   • 使用 scanf 读取输入的 n，直到 n 为0为止。
   • 对于每个 n，调用 getphi 函数计算 φ(n) 并输出结果。

复杂度分析

• 时间复杂度：质因数分解的时间复杂度为 O(sqrt(n))，因为最多需要遍历到 sqrt(n)。
• 空间复杂度：O(1)，只使用了常数级别的额外空间。

总结

通过质因数分解和应用欧拉函数的公式，我们可以高效地计算出 φ(n)。这种方法避免了逐个检查每个数是否与 n 互质，显著提高了计算效率，尤其适用于大数（n 高达1,000,000,000）的情况。