欧拉函数 定义：φ(n) 表示小于等于n的数中与n互质的数的个数。 基本性质： ① φ(1)=1 (很显然） ②对于φ(n)，如果n是质数，φ(n) = n - 1。 （也很显然） ③对于φ(n)，如果n是质数p的k次方(即n=p^k),对于φ(n) = p^k - p^(k-1)。想了半天终于想懂为什么了。n是质数p的k次方，那么除了p的倍数其他的数都跟n互质，p的倍数有多少个呢。自然是n/p个了（相当于15里面有15/3个3的倍数），n/p就是p^(k-1)。 ④若n.m互质，φ(nm) = φ(n) * φ(m)。 ⑤ 当n为奇数时，φ(2*n)=φ(n)。 ⑥当n是质数时，φ(n * 2) = φ(n) * φ(2) = φ(n)。 ⑦小于N且与N互质的所有数的和是φ(n)*n/2。
然后根据这些我们就可以求出欧拉函数来了。 代码：
int phi[maxn]; //储存欧拉函数的值 void GetPhi() { for(int i = 1; i < maxn; i++) phi[i] = i; for(int i = 2; i < maxn; i++) { if(phi[i] == i) { //证明i是质数 phi[i] = i - 1; for(int j = 2; j * i < maxn; j++) { phi[i * j] = phi[j * i] / i * (i - 1); } } } }这道题目的意思：
给出一些数字，对于每个数字找到一个欧拉函数值大于等于这个数的数，求找到的所有数的最小和。 思路：1.用数组存下每个数的欧拉函数值，然后一个个找。 2.利用欧拉函数的性质。对于给定的数x，欧拉函数值大于等于x的数一定大于x，于是我们从x+1开始找，看他之后的每一个数是不是素数，如果是的话，就break。为什么呢，因为纵观刚刚的那些性质我们发现，素数的欧拉函数值最大。所以我们碰到的第一个素数一定是我们要找的数。 附第二种做法：
#include <bits/stdc++.h> using namespace std; const int maxn = 1e6 + 10; int data[maxn]; int ans[maxn], a[maxn]; bool notprime[maxn]; void init() { notprime[0] = notprime[1] = true; for(int i = 2; i < maxn; i++) { if(notprime[i]) continue; for(int j = 2; j * i < maxn; j++) { notprime[i * j] = true; } } } int main() { int t, cas = 1, n, i, c, j; init(); scanf("%d", &t); while(t--) { long long sum = 0; scanf("%d", &n); for(i = 0; i < n; i++) { scanf("%d", &c); for(j = c + 1; ; j++) { if(!notprime[j]) { sum += j; break; } } } printf("Case %d: %lld Xukha\n", cas++, sum); } }