2025年降幂算法

大家好，我是讯享网，很高兴认识大家。

欧拉降幂公式

$a$ ^b $\equiv a$ ^{b% $φ (p)$ + $φ (p)$} $(m o d p)$ $（ b > φ (p) ）$

可以把大指数转化成不超过 $φ (p)$ 的指数。
注意，这里不要求a,p互质。
注意，这里不要求a,p互质。
注意，这里不要求a,p互质。（重要的事情说三遍！！！）
证明就不说啦，太菜了…

费马小定理

首先p是一个质数， $a$ ^p $\equiv a (m o d p)$ 。若gcd(a,p)=1时， $a$ ^p-1 $\equiv 1 (m o d p)$ ；若gcd(a,p)=p， $a$ ^p-1 $\equiv 0 (m o d p)$
可以看出费马小定理是欧拉的特殊情况，即p是质数， $φ (p) = p - 1 。$

传送门：Days passing

题意： 已知当前是周几，求 $N^M(1<=N<10$ ¹⁰⁰⁰⁰ $, 6 < = M < 10000, M 是 6 的整数倍)$ 天后是周几。
解析： 根据费马小定理：7是质数，
如果N是7的倍数， $N^M$ %7=0，周数不变，
如果N不是7的倍数， $N^M$ %7=1，周数向前一天。
代码：

#include<bits/stdc++.h> using namespace std; char N[10010]; string str; int n=0,m; int main(){ 
    cin>>str; scanf("%s",N+1); scanf("%d",&m); int len=strlen(N+1); for(int i=1;i<=len;i++){ 
    n=(n*10+N[i]-'0')%7; } if(n==0) cout<<str<<endl; else { 
    if(str=="Mon") cout<<"Tue"; else if(str=="Tue") cout<<"Wed"; else if(str=="Wed") cout<<"Thu"<<endl; else if(str=="Thu") cout<<"Fri"<<endl; else if(str=="Fri") cout<<"Sat"<<endl; else if(str=="Sat") cout<<"Sun"<<endl; else if(str=="Sun") cout<<"Mon"<<endl; } return 0; }

讯享网

传送门：sum

题意： 由1个数，2个数，3个数，…，n个数相加等于N（N为大整数）的不同情况有多少种。
解析： 用挡板法，假设N=3，有：1 1 1，有两个间隙。一个数时不需要加挡板为C(2,0)，两个数时加一个挡板为C(2,1)，三个数时加两个挡板为C(2,2).那么其实就是求：C(N-1,0)+C(N-1,1)+C(N-1,2)+…+C(N-1,N-1)=2^N-1。
答案mod 1e9+7。那么就对N进行大整数模拟取模1e9+6,最后再-1。再用快速幂即的答案。
代码：

讯享网#include<iostream> #include<stdio.h> #include<string.h> using namespace std; const int mod=1e9+7; char s[]; int N[]; int main(){ 
    while(~scanf("%s",s+1)){ 
    int len=strlen(s+1); long long sum=0; for(int i=1;i<=len;++i){ 
    sum=(sum*10+s[i]-'0')%(mod-1); } sum--; long long ans=1,tmp=2; while(sum){ 
    if(sum&1) ans=(ans*tmp)%mod; tmp=(tmp*tmp)%mod; sum/=2; } cout<<ans<<endl; } return 0; }

传送门：上帝与集合的正确用法

题意： 在这里插入图片描述
解析： 考虑欧拉降幂，f(p ) =2^{2%oula(p )+p}%p ，f(oula(p ))=2^{2%oula(oula(p ) )+oula(p )}%oula(p )，可以看出这是一个递推式，如果直接递推时间复杂度是否可行？
p到oula(p ) =p*(1-p/p₁)…*(1-p/p_n)。当p是偶数，一定有p₁=2，会乘上1/2；当p是奇数，oula(p )一定是偶数，因为它包含奇数质因子1-（1/奇数）会产生偶因子。
代码：

#include<bits/stdc++.h> #include<algorithm> using namespace std; int oula(int n){ 
    int rea=n; for(int i=2;i*i<=n;i++){ 
    if(n%i==0){ 
    rea=rea-rea/i; do{ 
    n/=i; }while(n%i==0); } } if(n>1) rea=rea-rea/n; return rea; } int qp(int a,int b,int p){ 
    int ans=1,tmp=a; while(b){ 
    if(b&1) ans=(1ll*ans*tmp)%p; tmp=(1ll*tmp*tmp)%p; b/=2; } return ans; } map<int,int> mmp; int f(int p){ 
    if(mmp[p]!=0) return mmp[p]; int ol=oula(p); if(p==1||p==2){ 
    return 0; } int t=qp(2,f(ol)+ol,p); mmp[p]=t; return t; } int main(){ 
    int T; scanf("%d",&T); while(T--){ 
    int p; scanf("%d",&p); printf("%d\n",f(p)); } return 0; }