博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
关于欧拉函数
阅读量:5055 次
发布时间:2019-06-12

本文共 1223 字,大约阅读时间需要 4 分钟。

欧拉函数,

对正整数n,欧拉函数是少于或等于n的数中与n互质的数的数目。
这是我在ACM队内训练赛的时候遇到的一个函数,其实最初是在离散数学课本上了解到了这个函数,但是当时并没有留下太深的印象,现在总结一下。
首先要知道欧拉函数的公式:euler(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…(1-1/pn)
其中p1,p2,p3是x的所有质因子。
1.第一种算法:
直接求法:
暴力遍历x的所有质因子直接求解:

int euler(int n){ //返回euler(n)        int res=n,a=n;       for(int i=2;i*i<=a;i++){           if(a%i==0){               res=res/i*(i-1);//先进行除法是为了防止中间数据的溢出                while(a%i==0) a/=i;           }       }       if(a>1) res=res/a*(a-1);       return res;  }

其中while(a%i==0) a/=i; 是在进行保证可以整除的是素数的过程。

另外,for(int i=2;i*i<=a;i++)也利用了素数筛选法的思想。

2.第二种算法:

筛选法打表求欧拉函数

#define Max 1000001  int euler[Max];  void Init(){        euler[1]=1;       for(int i=2;i

打表求值,不断求得。

2017-06-26 17:43:32 星期一 更新

今天在《算法竞赛入门(第二版)》(紫书)上看到了一种利用类似与素数筛选法的方法直接求由1~n的所有欧拉函数值的办法。
给出代码:

int pi[50001+10];const int maxn=50001;int euler(int n){    memset(pi,0,sizeof(pi));    pi[1]=1;    for(int i=2;i<=n;i++)        if(!pi[i])    {        for(int j=i;j<=n;j+=i)        {            if(!pi[j])                pi[j]=j;            pi[j]=pi[j]/i*(i-1);        }    }}

利用这个办法可以在nloglogn的复杂度内求得由1到n的所有欧拉函数值。

2017-08-09  12:48:12

新增一些欧拉函数的性质:

1.如果一个数x是素数,则该数的欧拉函数值为x-1。

2.若m,n互质,

 
3.当n为奇数时,
 

转载于:https://www.cnblogs.com/DLKKILL/p/7245254.html

你可能感兴趣的文章
Android 自定义View (三) 圆环交替 等待效果
查看>>
设置虚拟机虚拟机中fedora上网配置-bridge连接方式(图解)
查看>>
HEVC播放器出炉,迅雷看看支持H.265
查看>>
[置顶] Android仿人人客户端(v5.7.1)——人人授权访问界面
查看>>
Eclipse 调试的时候Tomcat报错启动不了
查看>>
【安卓5】高级控件——拖动条SeekBar
查看>>
ES6内置方法find 和 filter的区别在哪
查看>>
Android入门之文件系统操作(二)文件操作相关指令
查看>>
Android实现 ScrollView + ListView无滚动条滚动
查看>>
Swift 中的指针使用
查看>>
Swift - 使用闭包筛选过滤数据元素
查看>>
alue of type java.lang.String cannot be converted to JSONObject
查看>>
搜索引擎选择: Elasticsearch与Solr
查看>>
JAVA设计模式之简单工厂模式与工厂方法模式
查看>>
③面向对象程序设计——封装
查看>>
【19】AngularJS 应用
查看>>
Spring
查看>>
Linux 系统的/var目录
查看>>
Redis学习---Redis操作之其他操作
查看>>
WebService中的DataSet序列化使用
查看>>