欧拉函数模板

<span style="font-family: Arial, Helvetica, sans-serif;">#include <cstdio></span> #include <iostream> #include <string> #include <cmath> #include <algorithm> #include <cstring> #include <queue> #include <map> #include <stack> #define INF 0x3f3f3f3 #define MAX_N 3000005 using namespace std; long long euler[MAX_N]; void Euler() { for(int i = 1; i<MAX_N; i++) euler[i] = i; for(int i = 2; i<MAX_N; i++) { if(euler[i] == i) for(int j = i; j<MAX_N; j+=i) euler[j] = (euler[j]/i)*(i-1); } }

这是另一种实现方法

void init() { int i,j; for (i=1;i<N;i++) e[i]=i; for (i=2;i<N;i++) if (e[i]==i) { e[i]=i-1; for (j=i*2;j<N;j+=i) e[j]=e[j]/i*(i-1); } }