欧拉函数预处理 c++

在C++中，您可以使用预处理指令和循环来实现欧拉函数的预处理。以下是一个示例代码：

#include <iostream>
using namespace std;

const int MAX_N = 1000000;
int phi[MAX_N + 1];

void computePhi() {
    for (int i = 1; i <= MAX_N; i++) {
        phi[i] = i; // 初始化phi数组为各个数本身
    }
    
    for (int p = 2; p <= MAX_N; p++) {
        if (phi[p] == p) { // 如果当前数是素数
            for (int i = p; i <= MAX_N; i += p) {
                phi[i] -= phi[i] / p; // 将i的倍数的phi值减去 phi[i] / p
            }
        }
    }
}

int main() {
    computePhi();
    
    // 使用示例
    int n;
    cout << "请输入一个正整数n：";
    cin >> n;
    
    cout << "欧拉函数phi(" << n << ") = " << phi[n] << endl;
    
    return 0;
}

上述代码中，首先定义了一个全局数组`phi`，用于存储欧拉函数的预处理结果。`computePhi`函数通过两层循环计算欧拉函数的值，并将结果存储在`phi`数组中。在主函数中，您可以输入一个正整数n，然后输出其对应的欧拉函数值。

请注意，由于预处理需要遍历较大的范围，如果MAX_N的值很大，可能会导致较长的计算时间和较大的内存消耗。您可以根据实际需求调整MAX_N的大小。

希望这对您有所帮助！如果您有任何其他问题，请随时提问。