[关闭]
@Junlier 2018-11-08T08:56:22.000000Z 字数 2446 阅读 4477

欧拉函数&欧拉定理&降幂 总结

数学方法——数论
阅读体验:https://zybuluo.com/Junlier/note/1300214
这年头不总结一下是真的容易忘,老了老了,要AFO了。。。

欧拉函数

介绍

欧拉函数写做,表示中与互质的数的个数
那么我们会有引理(对于素数):


据说还有一个总的公式: (的质因子)

怎么求

线性筛所有欧拉函数

我们可以用线性筛素数的方法同时把欧拉函数筛出来(根据上面的引理)
不会线性筛素数?那你把这个板子背了就会了。。。笑哭.
(去掉和数组有关的就是线性筛素数了)
背板子吧,其实也容易理解

  1. void Prepare_Phi()
  2. {
  3. phi[1]=1;
  4. for(int i=2;i<=M;++i)
  5. {
  6. if(!phi[i])pri[++tot]=i,phi[i]=i-1;//①
  7. for(int j=1;j<=tot;++j)
  8. {
  9. if(i*pri[j]>M)break;
  10. if(!(i%pri[j]))
  11. {
  12. phi[i*pri[j]]=phi[i]*pri[j];//②
  13. break;
  14. }else phi[i*pri[j]]=phi[i]*(pri[j]-1);//③
  15. }
  16. }
  17. }

根号求单个欧拉函数

  1. il lst euler(rg lst x)
  2. {
  3. rg lst ans=x,tp=sqrt(x);
  4. for(lst i=2;i<=tp;++i)
  5. if(x%i==0)
  6. {
  7. ans=ans-ans/i;
  8. while(x%i==0)x/=i;
  9. }
  10. if(x>1)ans=ans-ans/x;
  11. return ans;
  12. }

欧拉定理

有了欧拉函数做坚实的后盾
讲欧拉定理就不用扯那些七里八里的东西了
一个公式:互质时

不知道怎么用对吧,那这样:
如果互质,那么有
也就是 互质

最有用的

PS:结合后面的扩展欧拉定理可以用作降幂,后面讲

扩展欧拉定理

嗯,一般扩展不就是把互质推广到所有情况嘛
行,如果上面那个式子里面不互质了

降幂(应用草鸡广的)

根据上面两个定理的公式结合起来

其实我们完全可以不用用到第一个
思考一下
是不是对于一个问题求
可以直接根据右边的条件把式子转换成上面三个中的一个
降幂成功
给个例题吧:洛谷P4139 上帝与集合的正确用法
代码你要吗?不要我也给你,虽然丑

  1. #include<bits/stdc++.h>
  2. #define lst long long
  3. #define ldb double
  4. #define N 10000050
  5. #define M 10000000
  6. using namespace std;
  7. const int Inf=1e9;
  8. int read()
  9. {
  10. int s=0,m=0;char ch=getchar();
  11. while(!isdigit(ch)){if(ch=='-')m=1;ch=getchar();}
  12. while( isdigit(ch))s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
  13. return m?-s:s;
  14. }
  15. int Q,tot;
  16. int phi[N],pri[N];
  17. void Prepare_Phi()
  18. {
  19. phi[1]=1;
  20. for(int i=2;i<=M;++i)
  21. {
  22. if(!phi[i])pri[++tot]=i,phi[i]=i-1;//①
  23. for(int j=1;j<=tot;++j)
  24. {
  25. if(i*pri[j]>M)break;
  26. if(!(i%pri[j]))
  27. {
  28. phi[i*pri[j]]=phi[i]*pri[j];//②
  29. break;
  30. }else phi[i*pri[j]]=phi[i]*(pri[j]-1);//③
  31. }
  32. }
  33. }
  34. lst qpow(lst x,lst y,lst mod)
  35. {
  36. lst ret=1;
  37. while(y)
  38. {
  39. if(y&1)ret=ret*x%mod;
  40. x=x*x%mod,y>>=1;
  41. }return ret;
  42. }
  43. lst Solve(lst mod)
  44. {
  45. if(mod==1)return 0;
  46. return qpow(2,Solve(phi[mod])+phi[mod],mod);
  47. }
  48. int main()
  49. {
  50. Prepare_Phi();
  51. Q=read();
  52. while(Q--)
  53. {
  54. int p=read();
  55. printf("%lld\n",Solve(p));
  56. }
  57. return 0;
  58. }

那,讲完了啊。。。你以为能讲多少。。。
毕竟我是个菜鸡嘛

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注