http://poj.org/problem?id=2407
题意:求少于或等于n的数中与n互质的数的数目。(n不大于10亿)
Sample Input
7
12
0
Sample Output
6
4
欧拉函数
在数论,对正整数n,欧拉函数是少于或等于n的数中与n互质的数的数目。此函数以其首名研究者欧拉命名,它又称为Euler's totient function、φ函数、欧拉商数等。 例如φ(8)=4,因为1,3,5,7均和8互质。 从欧拉函数引伸出来在环论方面的事实和拉格朗日定理构成了欧拉定理的证明。
φ函数的值 Euler函数
通式:φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn)
其中p1, p2……pn为x的所有质因数,x是不为0的整数
φ(1)=1(唯一和1互质的数就是1本身)【注意:每种质因数只一个。比如12=2*2*3】
定理:
若n是素数p的k次幂,φ(n)=p^k-p^(k-1)=(p-1)p^(k-1),因为除了p的倍数外,其他数都跟n互质
欧拉函数是积性函数——若m,n互质,φ(mn)=φ(m)φ(n)
证明:
若n= ∏ p^α
则φ(n)=∏(p-1)p^(α-1)=n∏(1-1/p)
∵欧拉函数是积性函数
所以有:φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn)
特殊性质:当n为奇数时,φ(2n)=φ(n), 证明于上述类似
特殊地,p是素数,φ(p) = p - 1,φ(p)称为p的欧拉值
简单套公式:
#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
#include <set>
//#include <map>
#include <queue>
#include <utility>
#include <iomanip>
#include <stack>
#include <list>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
//#include <ctime>
#include <ctype.h>
using namespace std;
int Euler (int n)
{
int i, res = n; //公式的x
for (i = 2; i * i <= n; i++)
{
if (n % i == 0)
{
n /= i;
res = res - res / i; //公式
while (n % i == 0)
n /= i;
}
}
if (n > 1)
res = res - res/n; //公式
return res;
}
int main()
{
int n;
while (scanf ("%d", &n), n)
printf ("%d\n", Euler(n));
return 0;
}
分享到:
相关推荐
欧拉函数 C语言实现 #include "iostream" #include "math.h" #define maxsize 100 using namespace std; typedef struct node { int num; int total; }struct_num; struct_num a[maxsize]; int is_prime(int n)
欧拉函数是数论中很重要的一个函数,欧拉函数是指:对于一个正整数 n ,小于 n 且和 n 互质的正整数(包括 1)的个数,记作 φ(n) 。 完全余数集合: 定义小于 n 且和 n 互质的数构成的集合为 Zn ,称呼这个集合为...
视频讲解欧拉定理和欧拉函数的证明。详细解释了证明简化剩余系的关系为什么要先证明完全剩余系的关系。以及欧拉函数的计算。
组合数学中经典定理 的实现 其中有: cayley定理 mobius 定理 欧拉函数 序数法 整数拆分等
给出了欧拉函数的部分性质的证明
采用主成分分析法判断了北京2000-2010年的经济活力。采用遗传算法优化的神经元网络模型评估10个城市的经济活力,马尔可夫灰度预测预测未来5年的发展状况。
封装好的扩展欧几里得、模幂运算及欧拉函数算法代码
主要介绍了PHP简单实现欧拉函数Euler功能,简单说明了欧拉函数的概念、原理,并结合实例形式分析了php实现欧拉函数的相关操作技巧,需要的朋友可以参考下
利用容斥原理对欧拉函数进行了推广,得出如下结论:1 )给出了欧拉函数的3 种初步推广,即函数φr;k (m),Ωr;k;l (m),Hr;k;l (m),找到并证明了r= 0 的 3 个表达式;2 )进一步推广了欧拉函数,得到并...
简化剩余系和欧拉函数.ppt
算法-数论- 欧拉函数.rar
能够在线性时间内筛出素数,并且对于计算欧拉函数值
简化剩余系与欧拉函数PPT学习教案.pptx
代码实现,欧拉函数代码实现,matlab源码
欧拉函数 1
hdu 1695 GCD(欧拉函数+容斥原理).docx
欧拉迭代,简单欧拉法迭代,二阶。可替换不同函数
讲义204-第二章第四讲-欧拉函数的计算(2023-1005,周四34).pdf
Not矩阵的广义平方根及其在隐逻辑算子揭示和全矩阵圆欧拉函数定义中的应用_Generalized Square roots of Not matrices, their application to the unveiling of hidden logical operators and to the definition of ...
拉格朗日插值法 该项目基于Spring Boot结合thymeleaf模板引擎实现,实现了6个常见的数值分析算法。...主要实现了拉格朗日插值法、牛顿插值法、直线拟合、多项式二次曲线拟合、复化梯形公式、欧拉函数.zip