欧拉函数
欧拉函数，对于正整数n，欧拉函数就是小于或者等于n的数中与n互质的数的数目。
通式为：
F(x) = x * (1 – 1 / p1) * (1 – 1 / p2) * ……. * (1 – 1 / pn)；p1，p2，p3…..pn为x的质因子。每一质因子只出现一次。即p1 ≠ p2 ≠ ….pn； 例如12 = 2 * 2 * 3；2只能算一次。
有了这个欧拉通式，便可以快速的求解这一题，该开始我是用普通的方法做的，很明显，超时了，一次输入的数很多个的时候，便容易超时。
下面是AC的代码：
#include <iostream>using namespace std;#define MAX 33000int a[MAX];void make_eular()//打表{a[1] = 1;for(int i = 2; i < MAX; i++){a[i] = i;}for(int j = 2; j < MAX; j++)//求解每一个的欧拉函数，{if(a[j] == j){for(int k = j; k < MAX; k += j) //从j到MAX，每一个数，有质因子为j的k，计算一次。加上外循环，，也就是j那层，便将每一个数的欧拉函数{//都计算出来了。a[k] = a[k] / j * (j – 1);}}}}int main(){int n, t;make_eular();cin >> t;while(t–){cin >> n;cout << a[n] << endl;}return 0;}
觉得自己做的到和不做的到，其实只在一念之间
