数学|[BZOJ 3884] 上帝与集合的正确用法【欧拉定理/初等数论】
[Description]求值
![数学|[BZOJ 3884] 上帝与集合的正确用法【欧拉定理/初等数论】](https://img.it610.com/image/info8/74a96f314bc94cef95693ea0149d5ccc.gif)
文章图片
[Solution]
不要被无限个2吓到了，这一题有一些有趣的性质可以发掘的。
这里介绍两个解法。
· Solution 1
我们温习一下欧拉定理：
![数学|[BZOJ 3884] 上帝与集合的正确用法【欧拉定理/初等数论】](https://img.it610.com/image/info8/50c34118cd3745eca3004d8c1ebc6553.gif)
文章图片
和它的推广：
![数学|[BZOJ 3884] 上帝与集合的正确用法【欧拉定理/初等数论】](https://img.it610.com/image/info8/ebf31ccafdf0499ca7a8f228d0b84097.gif)
文章图片
我们发现，这题的n,p并不一定互素啊，怎么办呢？我们可以让他们强行互素。
利用公式：
![数学|[BZOJ 3884] 上帝与集合的正确用法【欧拉定理/初等数论】](https://img.it610.com/image/info8/e865c50f81d64d30a7bddc326e11fbe0.gif)
文章图片
我们把原题中的p分为2^k+y
所以原式化为
![数学|[BZOJ 3884] 上帝与集合的正确用法【欧拉定理/初等数论】](https://img.it610.com/image/info8/81cf49ec1e0b4369a27b295d80416b2e.gif)
文章图片
此时y是奇数，和指数互质了！然后就可以愉快地使用欧拉定理–原式化为
![数学|[BZOJ 3884] 上帝与集合的正确用法【欧拉定理/初等数论】](https://img.it610.com/image/info8/f35a44018bbc4aaf858e921f4d9869c8.gif)
文章图片
我们发现中间的指数一部分又与原问题相似，于是想到可以递归求解。
那边界是什么呢？我们发现，phi(y)会不断缩小，而且每次至少会除去一个2，所以递归的深度最多为log2(p),当y=1时，返回0即可。
需要事先筛好phi值或者直接需要的时候根号时间计算求解。
复杂度O(p+log2(p))–线性筛/O(log2(p)*sqrt(p))–直接计算。
实践过程中第二种方法远远快于第一种。
· Solution 2
还是根据公式
文章图片
设答案为f(p),有
![数学|[BZOJ 3884] 上帝与集合的正确用法【欧拉定理/初等数论】](https://img.it610.com/image/info8/d20974dc818845d2b0362ae70e992d65.gif)
文章图片
同样递归求解即可，复杂度同第一个解。
[Code]
给出两种解法的代码，第一种用的线性筛，第二种直接求解。
· Code 1
#includetypedef long long ll;
const int maxn=10000001;
int phi[maxn]={0,1};
void MakePhiList(){
for(int i=2;
i>=1;
}
return ans;
}ll f(int x){
if(x==1) return 0;
int k=0;
while(!(x%2)) x/=2,k++;
return pow(2,(f(phi[x])%phi[x]-k%phi[x]+phi[x])%phi[x]+phi[x],x)< 【数学|[BZOJ 3884] 上帝与集合的正确用法【欧拉定理/初等数论】】· Code 2
#include
#includetypedef long long ll;
int Phi(int x){
int ans=x;
for(int i=2,lim=sqrt(x)+1;
i1?ans-ans/x:ans;
}ll pow(ll a,ll n,ll p){
ll ans=1;
while(n){
if(n&1) ans=ans*a%p;
a=a*a%p;
n>>=1;
}
return ans;
}ll f(int x){
if(x==1) return 0;
int phi=Phi(x);
return pow(2,f(phi)+phi,x);
}int main(){
int kase;
scanf("%d",&kase);
while(kase--){
int x;
scanf("%d",&x);
printf("%lld\n",f(x));
}
return 0;
} 推荐阅读
- 数学大作战
- 2019.11.14号总结
- 五年级数学上册期中考试质量分析
- 思维导图让你换一种打开方式学数学
- 读《吴正宪给小学数学教师的建议》有感
- 湘潭大学“三下乡”（羊牯村采访）
- 【思维导图实战派】刻意练习计划“遇见……”|【思维导图实战派】刻意练习计划“遇见……” 1/300 人教版数学五下第三单元《正方体和长方体的认识》
- 俄语小数、分数、百分数、及简单数学公式的读法
- 拨动一代代数学家心弦的圆周与直径之比——圆周率发展简史
- 吴正宪老师让学生爱上数学的四点经验