引入：互质的概念：如果 正整数 a 与b 之间只有一个公约数1 则称a与 b 互为质数。
欧拉函数的定义： 1-N 中 与N 互质的数的个数 记作 Phi（N）
在算数基本定理中任意自然数能进行质因数拆分，那么由容斥原理：
1>假设N 的质因子由p1……p（k） 一共有k个;
2>从1到N 去掉p1……p（k）的所有倍数；p(i)的倍数的个数是 N/p（i）下取整；
3>发现有多去除的，所以每次加上所有p（i）*p(j)的倍数
4>以此类推 发现有多加的 减去所有 三个质数乘积的倍数 ~~~加上所有四个质数乘积的倍数。
这恰好就是欧拉函数展开的结果，不得不佩服欧拉斯人
从而得到 欧拉函数 Phi（N）=N*（1-1/p1）*(1-1/p2)*(1-1/p3)*(1-p4)*(1-p5)……*（1-1/pk）；
观察这个式子可知欧拉函数的值只与N 和N 的质因子种类数有关，而N 是确定的，因此，只要找出N的质因子的种类数，就容易得出欧拉函数的值。
这也是我们求欧拉函数值的时候重点关注的一点。
//给你n个正整数ai 是求出每个数的欧拉函数。
//示例为试除法求欧拉函数
#include<bits/stdc++.h>
using namespace std;
#define int long long
int tt;
signed main(){cin>>tt;while(tt--){int a;cin>>a;int res=a;for(int i=2;i<=a/i;i++){if(a%i==0) res=res/i*(i-1);while(a%i==0) a/=i;}if(a) res=res/i*(i-1);cout<<res<<endl;}return 0;
}2.筛法求欧拉函数
由欧拉函数性质我们可以借助线性筛出质数的同时求出欧拉函数的值。
证明一：如果x是质数，那么phi（x）=x-1。
如果x是质数，那么除了它自身以外的所有小于x的自然数都与x互质个数为 x-1.
证明二： 如果pj是小于x的一个质因子，那么phi（x*pj）=phi（x）*pj 。
首先我们假设 x的质因子分别是 p1、p2、....pk 那么因为 pj 是 x的一个质因子，可知pj 一定为 p1-pk 中的某一个质因子，那么把（x*pj）看作一个整体 由欧拉函数的定义得知 phi（x*pj)=(x*pj)*(1-1/p1)*(1-1/p2)*()........*(1-1/pk)(因为pj是p1到pk中的某一个质因子，所以x*pj 与x 的质因子种类是相同的) 那么进一步可得：
phi（x * pj）= pj *（x * (1-1/p1) * (1-1/p2) * ()........* (1-1 / pk) ）=pj * phi（x）；
后面这一部分恰好就是phi（x）；
得证。
证明三：如果pj不是小于x 的一个质因子那么phi（x*pj）=phi（x）*（pj-1）；
同样的我们首先假设一下 x的质因子分别是p1 、p2、p3.....pk; 那么把（x*pj）看作一个整体
他的质因子数只比原来的x多了一个就是 pj。
那么由欧拉函数可得 phi（x*pj）=（x*pj）*（1-1/p1）*(1-1/p2)*(1-1/p3)*......*(1-1/pk)*(1-1/pj);
那么整理后可得 phi（x*pj）=（1-1/p1）*(1-1/p2)*(1-1/p3)*......*(1-1/pk））*（1-1/pj）*pj;
前面这一部分就是phi（x）；
也就是 phi（x*pj）=phi（x）*（pj-1）；
有了上述这三条性质，我们就比较容易的利用线性筛法在O（N）的时间复杂度下，求出从一到N的所有欧拉函数的值了。
下面给出利用线性筛法来求欧拉函数值的代码：
eg：给定一个正整数 n，求 1∼n 中每个数的欧拉函数之和。n<1e6;
#include<bits/stdc++.h>
using namespace std;
#define int long long //脚注：这个代码为了避免暴int 使用了#define int long long 这一宏定义
const int N=1e6+10;
bool st[N];
int cnt,primes[N];//存储质数的数组
int phi[N];//欧拉函数数组
int sum_elur(int n){for(int i=2;i<=n;i++){if(!st[i]) primes[cnt++]=i,phi[i]=i-1;//如果没被筛过说明是质数利用证明一//枚举质数的倍数从2开始，在筛指数是顺带求一下欧拉函数值for(int j=0;primes[j]*i<=n;j++){st[primes[j]*i]=1;if(i%primes[j]==0) {//如果说pj是i 的一个质因子 利用证明二求欧拉函数的值。phi[primes[j]*i]=phi[i]*primes[j];break;//primes[j] 已经是i 的最小质因子了，不再进行枚举了。}phi[primes[j]*i]=phi[i]*(primes[j]-1);//如果pj 不是i 的一个质因子，利用证明三。}}int res=0;for(int i=1;i<=n;i++){res+=phi[i];//累加求和}return res+1;//因为省去了初始化 phi [1]=1，在答案上加1就行;
}
signed main(){int n;cin>>n;cout<<sum_elur(n)<<endl;return 0;
}放几个个例题比较好：
eg1.可见的点
在一个平面直角坐标系的第一象限内，如果一个点 (x,y)(x,y) 与原点 (0,0)(0,0) 的连线中没有通过其他任何点，则称该点在原点处是可见的。例如，点 (4,2)(4,2) 就是不可见的，因为它与原点的连线会通过点 (2,1)(2,1)。部分可见点与原点的连线如下图所示：编写一个程序，计算给定整数 N 的情况下，满足 0≤x，y≤N 的可见点 (x，y) 的数量（可见点不包括原点）。输入格式第一行包含整数 C，表示共有 C 组测试数据。每组测试数据占一行，包含一个整数 N。输出格式每组测试数据的输出占据一行。应包括：测试数据的编号（从 1 开始），该组测试数据对应的 N以及可见点的数量。同行数据之间用空格隔开。数据范围1≤N,C≤1000输入样例：
4
2
4
5
231
输出样例：
1 2 5
2 4 13
3 5 21
4 231 32549思路：题意的理解，题目实际上要求的是直线第一次经过的点的个数，那么对于 一个点p （x,y）如果说 x ，y 有最大公约数，设d=gcd（x,y）,则有（x/d,y/d）也在，也就是说，如果x ,y 有最小公倍数的话 那么这个点其实就和 （x/d,y/d）是等价的，是不会使得答案增加的，那么其实就是求所有没有最小公倍数的二元组<x,y>的个数，这样就完美的转换成了求互质对的个数，不妨固定一个y
我们预处理出所有小于y的且与y 互质的元素的个数，最后求和，这不就是欧拉函数吗，问题完美解决了
代码：
送你一堆样例,增强数感的版本^_^
#include<bits/stdc++.h>
using namespace std;
int n,c;
const int N=2e5+10;
int primes[N],cnt;
bool st[N];
int phi[N];
void init(int n){phi[1]=1;for(int i=2;i<=n;i++){if(!st[i]){primes[cnt++]=i; phi[i]=i-1; }for(int j=0;primes[j]<n/i;j++){st[primes[j]*i]=1;if(i%primes[j]!=0) phi[primes[j]*i]=phi[i]*(primes[j]-1);if(i%primes[j]==0){phi[i*primes[j]]=phi[i]*primes[j];break;}}}}
signed main(){init(N);
// for(int i=1;i<=N;i++){
// cout<<"i=="<<i<< "phi="<<phi[i]<<endl;
// }cin>>c;for(int i=1;i<=c;i++){int n;cin>>n;int ans=0;for(int j=2;j<=n;j++){ans+=phi[j];}cout<<i<<" "<<n<<" "<<2*ans+3<<endl;}return 0;
}
//1 1 3
//2 2 5
//3 3 9
//4 4 13
//5 5 21
//6 6 25
//7 7 37
//8 8 45
//9 9 57
//10 10 65
//11 11 85
//12 12 93
//13 13 117
//14 14 129
//15 15 145
//16 16 161
//17 17 193
//18 18 205
//19 19 241
//20 20 257
//21 21 281
//22 22 301
//23 23 345
//24 24 361
//25 25 401
//26 26 425
//27 27 461
//28 28 485
//29 29 541
//30 30 557
//31 31 617
//32 32 649
//33 33 689
//34 34 721
//35 35 769
//36 36 793
//37 37 865
//38 38 901
//39 39 949
//40 40 981
//41 41 1061
//42 42 1085
//43 43 1169
//44 44 1209
//45 45 1257
//46 46 1301
//47 47 1393
//48 48 1425
//49 49 1509
//50 50 1549
//51 51 1613
//52 52 1661
//53 53 1765
//54 54 1801
//55 55 1881
//56 56 1929
//57 57 2001
//58 58 2057
//59 59 2173
//60 60 2205
//61 61 2325
//62 62 2385
//63 63 2457
//64 64 2521
//65 65 2617
//66 66 2657
//67 67 2789
//68 68 2853
//69 69 2941
//70 70 2989
//71 71 3129
//72 72 3177
//73 73 3321
//74 74 3393
//75 75 3473
//76 76 3545
//77 77 3665
//78 78 3713
//79 79 3869
//80 80 3933
//81 81 4041
//82 82 4121
//83 83 4285
//84 84 4333
//85 85 4461
//86 86 4545
//87 87 4657
//88 88 4737
//89 89 4913
//90 90 4961
//91 91 5105
//92 92 5193
//93 93 5313
//94 94 5405
//95 95 5549
//96 96 5613
//97 97 5805
//98 98 5889
//99 99 6009
//100 100 6089
//101 101 6289
//102 102 6353
//103 103 6557
//104 104 6653
//105 105 6749
//106 106 6853
//107 107 7065
//108 108 7137
//109 109 7353
//110 110 7433
//111 111 7577
//112 112 7673
//113 113 7897
//114 114 7969
//115 115 8145
//116 116 8257
//117 117 8401
//118 118 8517
//119 119 8709
//120 120 8773
//121 121 8993
//122 122 9113
//123 123 9273
//124 124 9393
//125 125 9593
//126 126 9665
//127 127 9917
//128 128 10045
//129 129 10213
//130 130 10309
//131 131 10569
//132 132 10649
//133 133 10865
//134 134 10997
//135 135 11141
//136 136 11269
//137 137 11541
//138 138 11629
//139 139 11905
//140 140 12001
//141 141 12185
//142 142 12325
//143 143 12565
//144 144 12661
//145 145 12885
//146 146 13029
//147 147 13197
//148 148 13341
//149 149 13637
//150 150 13717
//151 151 14017
//152 152 14161
//153 153 14353
//154 154 14473
//155 155 14713
//156 156 14809
//157 157 15121
//158 158 15277
//159 159 15485
//160 160 15613
//161 161 15877
//162 162 15985
//163 163 16309
//164 164 16469
//165 165 16629
//166 166 16793
//167 167 17125
//168 168 17221
//169 169 17533
//170 170 17661
//171 171 17877eg2：最大公约数
给定整数 N，求 1≤x,y≤N 且 GCD(x,y) 为素数的数对 (x,y) 有多少对。GCD(x,y)即求 x，y的最大公约数。输入格式输入一个整数 N。输出格式输出一个整数，表示满足条件的数对数量。数据范围1≤N≤1e7输入样例：
4
输出样例：
4思路：还是从这个式子入手 gcd（x，y）的值是一个素数，假设 gcd（x，y）=p ，那么p|x 且 p|y，因为是最大公约数，所以必有x/p==1 or y/p==1,而我们知道 gcd（x/p,y/p）==gcd(x/p,1) or gcd(1,y/p)=1,这不就是互质的定义吗，我可以固定y /p求所有小于y /p的的与y/p 互质的数的个数，这不就是欧拉函数吗，我们只需枚举所有小于n 的所有质数，然后像第一题一样求欧拉函数的和就行
代码：
#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N=1e7+10;
int primes[N],cnt;
int st[N];
int phi[N];
long long sum[N];
void init(int n){phi[1]=1;for(int i=2;i<=n;i++){if(!st[i]){primes[cnt++]=i;phi[i]=i-1;} for(int j=0;primes[j]<=n/i;j++){st[primes[j]*i]=1;if(i%primes[j]==0){phi[primes[j]*i]=phi[i]*primes[j];break;}phi[i*primes[j]]=phi[i]*(primes[j]-1);}}for(int i=2;i<=n;i++){sum[i]=sum[i-1]+phi[i];}}signed main(){int n;cin>>n;init(n);LL ans=0;for(int i=0;i<cnt;i++){int p=primes[i];ans+=2*sum[n/p]+1;}cout<<ans<<endl; return 0;}
