欧拉降幂模板

公式

题目大意

给定一个长度为n的数组w，模数m和询问次数q，每次询问给定l,r，求：

对m取模的值。

代码

#include<bits/stdc++.h>
using namespace std;
#define maxn 101010
#define MOD(a,b) a>=b?a%b+b:a
#define ll long long
unordered_map<int,int>mp;
int n；//一共有n层
int q；//询问次数
int l,r;//如图
ll m;//模数
ll w[maxn];//底数
ll qpow(ll a,ll b,ll mod)
{
    ll res=1;
    while(b)
    {
        if(b&1)res=MOD(res*a,mod);
        a=MOD(a*a,mod);
        b>>=1;
    }
    return res;
}
ll phi(ll k)
{
    ll x=k,s=k;
    if(mp.count(k))return mp[k];
    for(int i=2;i*i<=k;i++)
    {
        if(k%i==0)s=1ll*s/i*(i-1);
        while(k%i==0) k/=i;
    }
    if(k>1)s=s/k*(k-1);
    mp[x]=s;
    return s;
}
ll solve(int id,ll mod)
{
    if(id==r||mod==1) return MOD(w[id],mod);
    return qpow(w[id], solve(id+1, phi(mod)), mod);
}
int main()
{
    scanf("%d%lld",&n,&m);
    for(int i=1;i<=n;i++)scanf("%lld",&w[i]);
    scanf("%lld",&q);
    while(q--)
    {
        scanf("%d%d",&l,&r);
        printf("%lld\n",solve(l,m)%m);
    }
    return 0;
}