欧拉降幂 解决极大${b}$的 $a^b\%p$

欧拉公式

${1∼N\,中与\,N\,互质的数的个数被称为欧拉函数,记为\,{\varphi}(N)\,}。$
$若在算数基本定理中,N=p_1^{a_1}p_2^{a_2}…p_m^{a_m}\,,则:$
${\quad}{\quad}{\quad}{\quad}{\quad}{\quad}{\quad}{\quad}{\quad}{\quad}{\quad}{\quad}{\quad}{\quad}{\quad}{\varphi}(N)\,=N\,×\frac{p_1-1}{p_1}×\frac{p_2-1}{p_2}×…×\frac{p_m-1}{p_m}$

欧拉定理

${\quad}{\quad}{\quad}{\quad}{\quad}{\quad}{\quad}{\quad}{\quad}{\quad}{\quad}{\quad}{\quad}{\quad}{\quad} (a,n)=1{\Rightarrow}a^{\varphi}(n)\,{\equiv}\,1\,(mod \, n)$

费马小定理

${\quad}{\quad}{\quad}{\quad}{\quad}{\quad}{\quad}{\quad}{\quad}{\quad}{\quad}{\quad}{\quad}{\quad}{\quad}p为质数{\Rightarrow}a^{p-1}\,{\equiv}\,1\,(mod\, p)$

扩展欧拉定理

${\quad}{\quad}{\quad}{\quad}{\quad}{\quad}{\quad}{\quad}{\quad}{\quad}{\quad}{\quad}{\quad}{\quad}{\quad}b{\lt}{\varphi}(n)时,a^b\,{\equiv}\,a^b\,({mod \, n})$

${\quad} {\quad} {\quad} {\quad} {\quad} {\quad} {\quad} {\quad} {\quad} {\quad} {\quad} {\quad} {\quad} {\quad} {\quad}{b{\geq}{\varphi}(n)}时,a^b\,{\equiv}\,a^{b\,{mod}\,{\varphi}(n)\,+\,{\varphi}(n)} \,({mod \,n})$

封装函数模板

ll ola_pow(ll a,ll d,ll u,ll p) {
    // a^(b)%p b=d^u
    // if gcd(a,p)=1 : a^b%p=a^(b%ola(p))%p
    // elif b<ola(p) : a^b%p=a^b%p=a^(b%ola(p))%p
    // elif b>=ola(p): a^b%p=a^(b%ola(p)+ola(p))%p
    ll ola_p=ola(p),ok=0,_=1;
    for(ll i=0;i<64&&i<=u;i++) {
        if(_>=ola_p) ok=1;
        _*=d;
    }
    return q_pow(a,q_pow(d,u,ola_p)+ok*ola_p,p);
}

模板题

欧拉降幂 代码

#define ll long long
ll q_pow(ll n,ll p,ll mod){
   ll ans=1;
   while(p){
      if(p&1)  ans=n*ans%mod;
      n=n*n%mod;
      p>>=1;
   }
   return ans;
}
ll ola(ll n){  //欧拉函数
    ll ans=n;
    for(ll i=2;i*i<=n;i++){
       if(n%i==0){
         ans=ans/i*(i-1);
         while(n%i==0) n/=i;
       }
    }
    if(n>1) ans=ans/n*(n-1);
    return ans;
}
ll ola_read(ll p){
   ll b=0,f=0;
   char ch;
   while(!isdigit(ch=getchar())) ; //处理缓冲区
   while(isdigit(ch)){
      b=b*10+ch-'0';
      if(b>=p) f=1;
      b%=p;
      ch=getchar();
   }
   return b+(f==1)*p;
}
void solve(){   //a^b%p 
    ll a,p;
    cin>>a>>p;
    ll b=ola_read(ola(p));
    cout<<q_pow(a,b,p);
}

2023河南萌新联赛第（三）场：郑州大学 F
欧拉降幂
首先上面的式子可以分解为:1+x^1+x^2+x^3+x^4+....+x^(2^(n+1)-1)
等比数列求和公式，同时注意公比为1的情况
1.不考虑模数是质数的不简化版本

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
ll q_pow(ll a,ll b,ll p=mod){
   ll ans=1;
   while(b){
      if(b&1)  ans=(a*ans)%p;
      a=(a*a)%p;
      b>>=1;
   }
   return ans;
}
ll ola(ll n){  //欧拉函数
    ll res=n;
    for(ll i=2;i*i<=n;i++){
       if(n%i==0){
         res=res/i*(i-1);
         while(n%i==0) n/=i;
       }
    }
    if(n>1) res=res/n*(n-1);
    return res;
}
ll inv(ll b,ll c=mod){
   return q_pow(b,c-2,c);
}
ll ola_pow(ll a,ll d,ll u,ll p) {
    // a^(b)%p b=d^u
    // if gcd(a,p)=1 : a^b%p=a^(b%ola(p))%p
    // elif b<ola(p) : a^b%p=a^b%p=a^(b%ola(p))%p
    // elif b>=ola(p): a^b%p=a^(b%ola(p)+ola(p))%p
    ll ola_p=ola(p),ok=0,_=1;
    for(ll i=0;i<64&&i<=u;i++) {
        if(_>=ola_p) ok=1;
        _*=d;
    }
    return q_pow(a,q_pow(d,u,ola_p)+ok*ola_p,p);
}
int main() {
    ll n,x;
    cin>>n>>x;
    x%=mod;
    if(x==1) {
        cout<<q_pow(2,n+1,mod)<<endl;
    }
    else {
        ll down_q=ola_pow(x,2,n+1,mod);
        cout<<((((down_q%mod-1)*inv(x-1))%mod+mod))%mod<<endl;
    }



    return 0;
}

2.考虑模数为质数的简化版本

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

constexpr int P = 998244353;

i64 power(i64 a, i64 b, int p = P) {
    i64 res = 1;
    for (; b; b >>= 1, a = a * a % p) {
        if (b & 1) {
            res = res * a % p;
        }
    }
    return res;
}

i64 inv(i64 x) {
    return power(x, P - 2);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    i64 n, x;
    cin >> n >> x;
    x %= P;

    if (x == 1) {
        cout << power(2, n + 1) << '\n';
    } else {
        i64 k = power(2, n + 1, P - 1);
        cout << (power(x, k) - 1 + P) % P * inv(x - 1) % P << '\n';
    }

    return 0;
}