注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

力的博客

小歇一会 heiheidemaolv

 
 
 

日志

 
 

HDU 2824 欧拉函数  

2012-03-30 20:57:30|  分类: ACM/C/C++/OJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

http://acm.hdu.edu.cn/showproblem.php?pid=2824

定义: 对于正整数n,φ(n)是小于或等于n的正整数中,与n互质的数的数目;
例如: φ(8) = 4, 因为1,3,5,7均和8互质。
性质:

1. 若p是质数,φ(p)= p-1.
2. 若n是质数p的k次幂,φ(n)= (p-1)p^(k-1)  因为除了p的倍数都与n互质
3. 欧拉函数是积性函数,即若m,n互质,φ(mn)= φ(m)φ(n)


根据这3条性质我们就可以退出一个整数的欧拉函数的公式,因为一个数总可以一些质数的乘积的形式。
E(k) = (p1-1)(p2-1)…(pi-1)*(p1^(a1-1))(p2^(a2-1))…(pi^(ai-1))
= k*(p1-1)(p2-1)…(pi-1)/(p1*p2*…pi)
= k*(1-1/p1)*(1-1/p2)…(1-1/pk)
在程序中利用欧拉函数如下性质,可以快速求出欧拉函数的值(a为N的质因数)
若(N%a==0 && (N/a)%a==0) 则有:E(N)=E(N/a)*a;
若(N%a==0 && (N/a)%a!=0) 则有:E(N)=E(N/a)*(a-1);

 

当数据比较小时,可以采取以下方式初始化欧拉数组:

void init()
{
      __int64 i,j;

      e[1] = 1;
      for(i=2;i<=N;i++)
            if(!e[i])
            { 
                         for(j=i; j<=N; j+=i)
                        { 
                               if (!e[j])
                                      e[j] = j;
                              e[j] = e[j] / i * (i-1);
                        } 
            }

}

 

数据比较大时利用素数筛选:

void init()
{
      __int64 i, j;
       p[0] = 1; //记录素数个数
       p[1] = 2;
      for (i=3; i<N; i+=2)
        {
              if (hash[i])
                  continue;
              p[++p[0]] = i;
              for (j=i*i; j<N; j+=i)
                      hash[j] = true;
        }         //筛素数
        e[1] = 1;
        for (i=1; i<=p[0]; i++)
                        e[p[i]] = p[i] - 1; //初始化素数的phi
       for (i=2; i<N; i++)
       {
                if(!e[i])
                {
                        for (j=1; j<=p[0]; j++)
                                if (i % p[j]==0)
                               {
                                                    if (i / p[j] % p[j])
                                                               e[i] = e[i / p[j]] * e[p[j]];
                                                    else
                                                               e[i] = e[i / p[j] ]* p[j];
                                                    break;
                                } // 利用上述性质求解
               } 
       }
       return ;
}

另外一个大牛的总结:

欧拉函数:

对于一个正整数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整除的正整数,则有 ap - 1 ≡ 1 mod p

证明这个定理非常简单,由于φ(p) = p-1,代入欧拉定理即可证明。
同样有推论:对于不能被质数p整除的正整数a,有ap ≡ a mod p

欧拉函数公式:


( 1 ) pk 的欧拉函数

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

 φ(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 为 n 的素因子的个数)
i=1
(注:∏是希腊字母,即π的大写形式,在数学中表示求积运算或直积运算,形式上类似于Σ,有时也用来代表圆周率值)

根据前面两个结论,很容易得出它的欧拉函数为:
I I
Φ(n) = ∏ piki -1(pi -1) = n ∏ (1 - 1 / pi)
i=1 i=1
对于任意 n > 2,2 | Φ(n) ,因为必存在 pi -1 是偶数。

AC代码:

#include <stdio.h>
#include <string.h>

#define MAX 3000010

__int64 f[MAX];


void init()
{
   int i,j;
    memset(f,0,sizeof(f));
   //f[0]=0;
    f[1]=1;  
   for(i=2;i<MAX;i++)
   {
      if(!f[i])
      {
         for(j=i;j<MAX;j+=i)
         {
            if(!f[j])
             f[j]=j;
            f[j]=f[j]/i*(i-1);
         }
      }
      f[i]+=f[i-1];
   }
   return;
}

int main()
{
   int a,b;
    init();  
   while(scanf("%d%d",&a,&b)==2)
   {
      //if(a>b)
       //a^=b^=a^=b;//ab交换,使用位运算法
      printf("%I64d\n",f[b]-f[a-1]);
   }
   return 0;
}

  评论这张
 
阅读(525)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018