xtuoj 欧拉函数

### XTUOJ 欧拉函数题目解题思路

#### 题目描述
XTU-OJ 1355-Euler’s Totient Function 是一道关于欧拉函数的经典题目。此题要求实现并计算给定整数 \( n \) 的欧拉函数值 φ(n)，即小于等于 \( n \) 并且与 \( n \) 互质的正整数的数量[^1]。

#### 解题方法概述
为了高效求解单个或多个查询中的欧拉函数，通常采用线性筛法来预处理所有可能的结果。这种方法不仅适用于单独数值的查询，也适合批量数据的快速响应。

#### 关键算法解释
对于任意自然数 \( n \)，其欧拉函数可以通过下面公式得到：

\[φ(n)=n(1−\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_k})\]

其中 \( p_i \) 表示能整除 \( n \) 的不同质因数。当遇到新的素因子时更新当前累积乘积即可完成一次有效的状态转移操作。

#### 实现细节说明
下面是基于上述理论的一个Python版本的具体实现方式:

def euler_sieve(max_n):
    phi = list(range(max_n + 1))
    
    for i in range(2, max_n + 1):
        if phi[i] == i:  # 如果i还是初始值，则它必然是一个素数
            for j in range(i, max_n + 1, i):
                phi[j] = phi[j] // i * (i - 1)

    return phi


if __name__ == "__main__":
    N = int(input())
    phis = euler_sieve(N)
    result = []
    for _ in range(int(input())):
        num = int(input().strip())
        result.append(str(phis[num]))
        
    print("\n".join(result))

这段代码首先定义了一个名为 `euler_sieve` 函数用于构建欧拉函数表；接着读取输入参数N表示最大范围内的数字，并调用该函数获取对应的phi列表；最后循环接收多组测试案例并将结果存储起来一次性输出。