The Euler function

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 1896    Accepted Submission(s): 769

Problem Description

The Euler function phi is an important kind of function in number theory, (n) represents the amount of the numbers which are smaller than n and coprime to n, and this function has a lot of beautiful characteristics. Here comes a very easy question: suppose you are given a, b, try to calculate (a)+ (a+1)+....+ (b)

 

 

Input

There are several test cases. Each line has two integers a, b (2<a<b<3000000).

 

 

Output

Output the result of (a)+ (a+1)+....+ (b)

 

 

Sample Input

3 100

 

 

Sample Output

3042

 

 

Source

 

 

Recommend

gaojie

 

 

 

 

 

 

 

 

 

欧拉函数：

 

低效的会TLE

code:

1 //高效  2 #include 
     
           3 #include 
      
            4 #include 
       
             5 #include 
        
              6 #include 
         
               7 #include 
          
            8 #include 
           
             9 #include 
            
              10 #include 
             
               11 #include 
              
                12 #include 
               
                 13 #include 
                
                  14 #include 
                 
                   15 #include 
                  
                    16 #include 
                   
                     17 #include 
                    
                      18 #include 
                     
                       19 #include 
                      
                        20 using namespace std; 21 22 __int64 phi[3000005]; 23 24 int main() 25 { 26 int i,j; 27 int N=3000005; 28 //------------------------------------------------------------------------------------ 29 for (i=1;i<=N;i++) //先除去因子2 30 phi[i]=(i&1)?i:i/2; 31 for (i=3;i<=N;i+=2) //找因子 32 if(phi[i]==i) //i的因子是否被全被找完（如i=9，i=15） 33 for(j=i;j<=N;j+=i) 34 phi[j]=phi[j]/i*(i-1); 35 /* 36 模拟： 37 假设N=18 38 i=3 39 phi[3]=3/3*2; 40 phi[6]=3/3*2 41 phi[9]=9/3*2 42 phi[12]=6/3*2 43 phi[15]=15/3*2 44 phi[18]=9/3*2 45 46 i=5 47 phi[5]=5/5*4 48 phi[10]=5/5*4 49 phi[15]=15/5*4 50 51 i=7 52 phi[7]=7/7*6 53 phi[14]=7/7*6 54 55 i=9 56 不会进入循环，因为此时phi[9]!=9 57 58 i=11 59 phi[11]=11/11*7 60 61 i=13 62 phi[13]=13/13*12 63 64 i=15 65 不会进入循环，因为此时phi[15]!=15 66 67 i=17 68 phi[17]=17/17*16 69 */ 70 //------------------------------------------------------------------------------------ 71 int n,m; 72 __int64 sum; 73 while(~scanf("%d%d",&n,&m)) 74 { 75 sum=0; 76 for(i=n;i<=m;i++) 77 sum+=phi[i]; 78 printf("%I64d\n",sum); 79 } 80 return 0; 81 } 82 83 84 85 86 /* 低效 87 88 #include 
                       
                         89 #include 
                        
                          90 using namespace std; 91 #define N 3000000 92 __int64 len,a[N+10],b[N+10],p[N+10]; 93 94 __int64 phi(int n) 95 { 96 int i,k=sqrt((double)n),ans=n; 97 for (i=0; i
                         
                          <=k;i++) //一个数的因子肯定小于根号n 98 { 99 if (n%p[i]==0) //找因子100 ans=ans/p[i]*(p[i]-1); //公式101 while(!(n%p[i]))102 {103 n/=p[i];104 }105 }106 if (n!=1) //找到未除尽的最后一个因子107 ans=ans/n*(n-1);108 return ans;109 }110 111 void init()112 {113 int i,j;114 len=0;115 //--------------------------素数筛选法--------------------------------------------------------116 for (i=2; i<=N; i++)117 a[i]=1;118 for (i=2; i<=sqrt((double)N); i++)119 if (a[i])120 for (j=i; j*i<=N; j++)121 a[j*i]=0;122 for (i=0; i<=N; i++)123 if (a[i])124 p[len++]=i;125 //--------------------------phi打表-----------------------------------------------------------126 for (i=4; i<=N; i++)127 if (!a[i])128 b[i]=phi(i);129 //--------------------------------------------------------------------------------------------130 }131 132 int main()133 {134 int n,m;135 init();136 while (~scanf("%d%d",&n,&m)) 137 {138 __int64 sum=0;139 for (int i=n;i<=m;i++)140 if(a[i])141 sum+=i-1;142 else143 sum+=b[i];144 printf("%I64d\n",sum);145 }146 return 0;147 }*/
                         
                        
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     

 

 

---

欧拉函数：

对于一个正整数n，小于n且和n互质的正整数的个数，记做：φ(n)，其中φ(1)被定义为1，但是并没有任何实质的意义。

特殊性质：当n为奇数时，φ(2n)=φ(n)。

完全余数集合：

定义小于n且和n互质的数构成的集合为Zn，称呼这个集合为n的完全余数集合。

显然，对于素数p，φ(p)= p - 1.

对于两个素数p、q，他们的乘积n = pq 满足φ(n) =(p-1)(q-1)

        证明：对于质数p,q，满足φ(n) =(p-1)(q-1)

        考虑n的完全余数集Zn = { 1,2,....,pq -1}

        而不和n互质的集合由下面三个集合的并构成：

        1) 能够被p整除的集合{p,2p,3p,....,(q-1)p} 共计q-1个

        2) 能够被q整除的集合{q,2q,3q,....,(p-1)q} 共计p-1个

        3) {0}

        很显然，1、2集合中没有共同的元素，因此Zn中元素个数 ＝ pq - (p-1 + q- 1 + 1) = (p-1)(q-1)

欧拉定理：

对于互质的整数a和n，有a^φ(n)  ≡ 1 mod n

{

注：

   同余符号：　　

    两个整数a，b，若它们除以整数m所得的余数相等，则称a，b对于模m同余

 

　　记作 a ≡ b (mod m)

 

　　读作a同余于b模m，或读作a与b关于模m同余。

 

　　比如 26 ≡ 14 (mod 12)

}

        证明：

        首先证明下面这个命题：

        对于集合Zn={x1,x2,...,xφ(n)}，考虑集合

        S = {ax1 mod n,ax2mod n,...,axφ(n)mod n}

        则S = Zn

        1) 由于a,n互质，xi也与n互质，则axi也一定于p互质，因此

        任意xi，axi mod n 必然是Zn的一个元素

        2) 对于Zn中两个元素xi和xj，如果xi ≠ xj

        则axi mod n ≠ axi mod n，这个由a、p互质和消去律可以得出。

        所以，很明显，S=Zn

       

        既然这样，那么

        （ax1 × ax2×...×axφ(n)）mod n

         = （ax1 mod n × ax2mod n × ... × axφ(n)mod n）mod n

         = （x1 × x2 × ... × xφ(n)）mod n

         考虑上面等式左边和右边

         左边等于(aφ(n) × （x1 × x2 × ... × xφ(n)）mod n) mod n

         右边等于x1 × x2 × ... × xφ(n)）mod n

         而x1 × x2 × ... × xφ(n)）mod n和p互质

         根据消去律，可以从等式两边约去，就得到：

          a^φ(n)  ≡  1 mod n

 

费马定理：

a是不能被质数p整除的正整数，则有 a^{p - 1}≡ 1 mod p

证明这个定理非常简单，由于φ(p) = p-1，代入欧拉定理即可证明。

同样有推论：对于不能被质数p整除的正整数a，有a^p ≡ a mod p

 

欧拉函数公式：

 

( 1 ) p^k 的欧拉函数

对于给定的一个素数 p ， φ(p) = p -1。则对于正整数 n = p^k ，

φ(n) = pk - pk -1  证明： 小于 pk 的正整数个数为 pk - 1个，其中 和 pk 不互质的正整数有{p * 1,p * 2,...,p * (pk - 1-1)} 共计 pk - 1 - 1 个 所以 φ(n) = pk - 1 - (pk - 1 - 1) = pk - pk - 1 。

( 2 ) p * q 的欧拉函数

假设 p, q是两个互质的正整数，则 p * q 的欧拉函数为

φ(p * q) = φ(p) * φ(q) ， gcd(p, q) = 1 。

证明： 令 n = p * q ， gcd(p,q) = 1 根据中国余数定理，有 Zn 和 Zp × Zq 之间存在一一映射 （我的想法是： a ∈ Zp ， b ∈ Zq ⇔ b * p + a * q ∈ Zn 。） 所以 n 的完全余数集合的元素个数等于集合 Zp × Zq 的元素个数。 而后者的元素个数为 φ(p) * φ(q) ，所以有 φ(p * q) = φ(p) * φ(q) 。

( 3 ) 任意正整数的欧拉函数

任意一个整数 n 都可以表示为其素因子的乘积为：

I n = ∏ piki i=1

（注：∏是希腊字母，即π的大写形式，在数学中表示求积运算或直积运算，形式上类似于Σ，有时也用来代表圆周率值）

根据前面两个结论，很容易得出它的欧拉函数为：           I                      I  Φ(n) = ∏  piki -1(p

_i

-1) = n ∏ (1 - 1 / pi)         i=1                    i=1 对于任意 n > 2，2 | Φ(n) ,因为必存在  p

_i

-1 是偶数。