题目链接：hdu 2824 The Euler function

计算欧拉函数，欧拉函数$\phi(x)$等于不超过$x$且与$x$互质的整数的个数。这里有两种求解方法：

方法一：

显然欧拉函数有如下三个性质：

1、$\phi(x=p) = p-1$，当$x$是质数时，$k\in[1,p-1]$的$p-1$个数都与$p$互质。

2、$\phi(x=p^n) = p^n - p^{n-1}$，当$x$是质数的$n$次方时，除了$p,2p,3p,\cdots,p^{n-1}p$这$p^{n-1}$个数以外的数都与$x$互质。

3、$\phi(x = ab) = \phi(a)\phi(b)$，当$x$等于两个数相乘时，其欧拉函数具有乘性。对于等式左边建立$\phi(ab)$个数的集合，对于等式右边建立$\phi(a)\phi(b)$个有序对，即从与$a$互质和与$b$互质的数的集合中各选一个组成有序对。根据中国剩余定理，可以发现这两个集合一一对应。

从而可以得到对任意整数$x$的欧拉函数值为：

\begin{equation} \phi(x = \prod_i^j p_i^{k_i} )= \prod_i^j p_i^{k_i} - p_i^{k_i-1} \end{equation}

 但是该方法需要对$x$进行质因数分解，因而编程实现的复杂度较高。

方法二：

对于求$\phi(x = \prod_i^j p_i^{k_i})$，可以使用容斥原理。即：

\begin{equation} \phi(x) = \sum_{S \subset\{p_i,i\in[1,j]\}} (-1)^{|S|} \frac{x}{\prod_{p_i\in S}p_i}\end{equation}

可以化简为：

\begin{equation} \phi(x) = x\prod_{i = 1}^j(1-\frac{1}{p_i})\end{equation}

原因是可以展开上式即从每一项中选择$1$或者$-\frac{1}{p_i}$，全部乘起来在乘以$x$得到。与2式定义相同。

对于该题，先使用筛法来求得给定范围内所有数的欧拉函数值，在进行求和。

代码如下：

 1 #include <cstdio> 2 #include <cstdlib> 3 #include <iostream> 4 #include <cstring> 5 #define     MAXN 3000003 6 using namespace std; 7 int phi[MAXN]; 8 void init() 9 {10     for( int i = 1 ; i < MAXN ; i++ )11     {12         phi[i] = i;13     }14     for( int i = 2 ; i < MAXN ; i++ )15     {16         if( phi[i] == i )17         {18             phi[i] = i -1;19             for( int j = i*2 ; j < MAXN ; j += i )20             {21                 phi[j] = phi[j]/i*(i-1);22             }23         }24     }25 }26 int main(int argc, char *argv[])27 {28     int a, b;29     init();30     while( scanf("%d%d", &a, &b) != EOF )31     {32         long long ans = 0;33         for( int i = a ; i <= b ; i++ )34         {35             ans += phi[i];36         }37         cout<<ans<<endl;38     }39 }

hdu 2824 The Euler function