题目链接

【模板】欧拉函数Ⅰ ‖ 单个整数

题目描述

给定一个正整数 ，求欧拉函数 的值。

欧拉函数 定义为：在 到 中与 互质的数的个数。

解题思路

本题要求我们求解单个整数的欧拉函数。我们可以直接利用欧拉函数的计算公式来解决。

欧拉函数的计算公式基于整数的唯一分解定理。设整数 的标准素数分解式为：

其中 是 的所有不同质因数。

则 的计算公式为：

为了方便在程序中计算，我们通常将公式变形为：

这个公式的计算过程可以和分解质因数的过程结合起来。具体算法如下：

  1. 初始化结果 ans = n。
  2. 从 开始，遍历到 。
  3. 如果 是 的一个因数，说明我们找到了一个质因数 。
    • 我们按照公式 来更新 ans。
    • 然后，将 中所有的因子 全部除掉，以确保我们只对每个不同的质因数计算一次。
  4. 遍历结束后，如果 仍然大于 ，说明 剩下的值本身也是一个大于 的质因数。
    • 我们同样需要对这个剩余的质因数 进行一次更新：。
  5. 最终得到的 ans 就是 的值。

这个算法通过试除法分解质因数，时间复杂度为 ，对于本题的数据范围是完全足够的。

代码

#include <iostream>

using namespace std;
using ll = long long;

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        ll n;
        cin >> n;
        cout << euler_phi(n) << "\n";
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    public static long eulerPhi(long n) {
        long ans = n;
        for (long i = 2; i * i <= n; ++i) {
            if (n % i == 0) {
                ans = ans / i * (i - 1);
                while (n % i == 0) {
                    n /= i;
                }
            }
        }
        if (n > 1) {
            ans = ans / n * (n - 1);
        }
        return ans;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            long n = sc.nextLong();
            System.out.println(eulerPhi(n));
        }
    }
}

def euler_phi(n):
    ans = n
    i = 2
    while i * i <= n:
        if n % i == 0:
            ans = ans // i * (i - 1)
            while n % i == 0:
                n //= i
        i += 1
    if n > 1:
        ans = ans // n * (n - 1)
    return ans

def main():
    t = int(input())
    for _ in range(t):
        n = int(input())
        print(euler_phi(n))

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法：数论、欧拉函数
  • 时间复杂度：对于每次查询，时间复杂度为 ，来自于试除法分解质因数。
  • 空间复杂度：，只需要常数个变量。