欧拉函数
函数 欧拉
2023-09-27 14:22:41 时间
欧拉函数
E(n)表示小于n的所有正数,与n互质的数的个数
1 当p为素数时,显然E(p)= p-1
2 当n=p^k (p为素数)时,E(p^k)=p^k-p^(k-1)
证明:小于n的数一共有p^k-1个,其中不与p互质的有p*1,p*2,p*3,…p*(p^(k-1)-1)(显然有p^(k-1)-1个),则E(n)=(p^k-1)-(p^(k-1)-1)=p^k-p^(k-1);
3 任何一个整数n都可以表示为n=(p1^a1)*(p2^a2)*…*(pn^an)
若ab互质,E(ab)=E(a)*E(b),欧拉函数为积性函数
E(n)=E(p1^a1)*E(p2^a2)*…*E(pn^an)
=(p1^a1-p1^(a1-1))*(p2^a2-p2^(a2-1))*…*(pn^an-pn^(an-1))
=(p1^a1*p2^a2*..*pn^an)*((1-1/p1)*(1-1/p2)*…*(1-1/pn))
=n*(1-1/p1)*(1-1/p2)*…*(1-1/pn)
4 E(p^k)=p^k-p^(k-1)=(p-1)*p^(k-1)
E(p^(k-1))=p^(k-1)-p^(k-2)=(p-1)*p^(k-2)
当k=1时,E(p)=p-1
当k>1时,E(p^k)=E(p^(k-1))*p
由上式,当p为素数时
若p是n的约数,E(n*p)=E(n)*p
否则,E(n*p)=E(n)*E(p)=E(n)*(p-1)
//求n的欧拉函数值,模板
#include"stdio.h" int phi(int n) { int i; int ans; ans=1; for(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; return ans; } int main() { int n; while(scanf("%d",&n)!=-1) printf("%d\n",phi(n)); return 0; }
相关文章
- C/C++ stat()函数:获取文件状态
- Matlab中abs函数的使用
- (《机器学习》完整版系列)第16章 强化学习——16.10 值函数近似
- 【BZOJ4173】数学 欧拉函数神题
- 【BZOJ3944/4805】Sum/欧拉函数求和 杜教筛
- 第八十五章 SQL函数 $LISTGET
- Oracle数据库:oracle嵌套分组函数(聚合函数),组函数的练习题,挺复杂的,用好decode函数,很有趣
- C++类中成员函数声明后面的const的含义
- HDU 1286 找新朋友 (欧拉phi函数打表)
- 【C语言】三种方法模拟实现strlen函数
- 窥探 Swift 之 函数与闭包的应用实例
- 关于反转函数的小知识
- 手把手教你搭建一个深度网络模型:从输入层-激活函数-损失函数-优化方法-输出层-执行训练
- poj 2154 Color 欧拉函数优化的ploya计数
- 【bzoj3518】点组计数 欧拉函数(欧拉反演)
- 【bzoj2705】[SDOI2012]Longge的问题 欧拉函数