euler证明
2024-08-31 01:11:44
我们用g(x)表示x的欧拉函数值,即1~x与x互质的数的个数
欧拉函数公式为: g(x)= y*((x1-1)/x1)*((x2-1)/x2)*((x3-1)/x3)....(其中x1, x2, x3....为质数)
证明:
1. 对于质数x,有g(x)=x-1
2. 对于x^h,其中x为质数,那么显然1~x^h之间包含x因子的数不与x^h互质,有:
x, 2*x, 3*x, 4*x.....x^(h-1)*x 共x^(h-1)个,很显然有g(x^h)=x^h-x^(h-1),其中x^(h-1)为
不与x^h互质的数。
例如:
y=3^4
... 3 .2*3.. 3*3 ..4*3. 5*3 3*3*3 .7*3..... 3*3*3*3
g(y)=3^4-3^3
3. 对于任意一个数y,我们可以将其分解成质数的积的形式,再由乘法原理得到g(y)
例如:
y=3^4*5^7
g(y)=(3^4-3^3)*(5^7-5^6)
4. 综上所述:
对于任意y=x1^h1*x2^h2*x3^h3......有:
g(y)=(x1^h1-x1^(h1-1))*(x2^h2-x2^(h2-1))*(x3^h3-x3^(h3-1))....
=x1^h1*(1-1/x1)*x2^h2*(1-1/x2)*x3^h3*(1-1/x3)....
=y*(1-1/x1)*(1-1/x2)*(1-1/x3)....
=y*((x1-1)/x1)*((x2-1)/x2)*((x3-1)/x3)....
至此得到了欧拉函数
代码:
/* int euler(int n){
int ans=1;
for(int i=2; i*i<=n; i++){
if(n%i==0){
ans*=(i-1);
n/=i;
while(n%i==0){
ans*=i;
n/=i;
}
}
}
if(n>1){
ans*=n-1;
}
}*/ int euler(int n){
int ans=n;
for(int i=; i*i<=n; i++){
if(n%i==){
ans=ans*(i-)/i;
while(n%i==){
n/=i;
}
}
}
if(n>){
ans=ans*(n-)/n;
}
}
最新文章
- 跟服务器交互的登录Demo
- 浅谈C# 多态的法力
- .net 导出Excel功能
- BZOJ3692 : 愚蠢的算法
- Azure 自动化:使用PowerShell Credential连接到Azure
- Java中的注解是如何工作的?--annotation学习一
- MySQL各个版本区别
- HDFS dfsclient写文件过程 源码分析
- python 安装预编译库注意事项-pip
- Ajax提交打开新窗口,浏览器拦截处理
- SQL Server 2008 批量插入数据时报错
- [转]于Fragment和Activity之间onCreateOptionsMenu的问题
- SSZipArchive的使用详解和遇到的问题
- 经典合集 - WP8.1数据源
- 在Html页面中调用ajax代码
- zabbix在执行docker命令是报错
- ota升级动画修改
- QSS-qt样式表
- 查看Windows端口及端口关闭方法
- aarch64_o1
热门文章
- LeetCode(88)题解-- Merge Sorted Array
- session.use_cookies有什么作用,
- 【BZOJ3782】上学路线 组合数+容斥+CRT
- EasyDarwin接入ffmpeg实现264转图片快照功能
- static 静态域 类域 静态方法 工厂方法 he use of the static keyword to create fields and methods that belong to the class, rather than to an instance of the class 非访问修饰符
- 【操作系统】使用BCD工具安装Ubuntu操作系统
- Android 启动过程介绍【转】
- 深入浅出剖析C语言函数指针与回调函数(一)【转】
- rc.local 开启自启动,检测是否成功
- 关于S50卡密钥A和密钥B