CodeForces906D

题意：

给定一个数列$w_1,w_2,...,w_n$和模数p,每次询问一个区间[l,r],求${\,{w_l}^{\,{w_{l+1}\,}^{\,{w_{l+2}\,}^{...^{w_r}\,}\,}\,}\,}mod\ p$的值。其中$1<=w_k<=10^9$，$1<=q<=10^5$。

思路：

有扩展欧拉定理：

$$a^n≡\begin{cases}a^{n\ mod\ \varphi(m)} & \gcd(a, m) = 1\\a^{n} & \gcd(a, m) \ne 1 \text{ 且 } n < \varphi(m)\\a^{n \bmod \varphi(m) + \varphi(m)} & \gcd(a, m) \ne 1 \text{ 且 } n \ge \varphi(m)\end{cases}\pmod {m}$$

由欧拉定理，有$a^{\varphi(m)} \equiv 1 \pmod{m}$，所以上式可以简单记为：

$a^n \equiv\begin{cases}a^{n} & n < \varphi(m)\\a^{n \bmod\varphi(m) + \varphi(m)} & n \ge \varphi(m)\end{cases}\pmod {m}$，

即$a^n\ mod\ m=a^{n\ mod\ \varphi(m)+(n>\varphi(m)?\varphi(m):0)}mod\ m$。

比如$a^{b^{c^d}}\ mod\ m=a^{b^{c^d}\ mod\ \varphi(m)+(b^{c^d}>\varphi(m)?\varphi(m):0)}\ mod\ m$，

其中$b^{c^d}\ mod\ \varphi(m)=b^{c^d\ mod\ \varphi(\varphi(m))+(c^d>\varphi(\varphi(m))?\varphi(\varphi(m)):0)}\ mod\ \varphi(m)$，

其中$c^d\ mod\ \varphi(\varphi(m))=c^{d\ mod\ \varphi(\varphi(\varphi(m)))+(d>\varphi(\varphi(\varphi(m)))?\varphi(\varphi(\varphi(m))):0)} \ mod\ \varphi(\varphi(m))$。

可以一直递归下去，$b^{c^d}\ mod\ \varphi(m)$可以递归处理。

如果l==r的时候，返回的是$d\ mod\ \varphi(\varphi(\varphi(m)))+(d>\varphi(\varphi(\varphi(m)))?\varphi(\varphi(\varphi(m))):0)$。

所以定义一个新的Mod方式：a<b?a:a%b+b。

递归的终点就是Mod(a[l],mod)。

如果$φ(φ(φ(⋯(n))))=1$，那么嵌套层数为$O(logn)$。

如果$φ(m)=1$了，那么可以在第二个式子返回0，之后都不用再继续递归了，这也是一个递归终点。

回溯的时候就可以用快速幂来计算了，比如先回溯到第三个式子，用正常的快速幂是ojbk的，但是回溯到第二个式子的时候会发现只计算了$c^d\ mod\ \varphi(\varphi(m))$这一部分，无法判断$c^d>\varphi(\varphi(m))$，所以用新定义的Mod方式来进行快速幂运算，这样子每次在函数中调用快速幂的时候得到的就是$c^d\ mod\ \varphi(\varphi(m))+(c^d>\varphi(\varphi(m))?\varphi(\varphi(m)):0)$整个的值啦，体现在式子里面就相当于改变了$c^d\ mod\ \varphi(\varphi(m))$这个快速幂的方式，那么返回的就是整个上上式的值啦。

注意计算$\varphi(m)$的时候要记忆化。

这里有个坑点，求$φ(n)$的时候，如果调用参数列表里的参数的话会TLE，如果自己在函数内部传个参，就不会TLE了，为什么时间差这么多这是什么玄学啊，难道用函数内部的变量更快？这还是第一次见这种状况。

代码：

#define Mod(a,b) a<b?a:a%b+b
typedef long long ll;
int n,l,r,q;
ll m;
ll a[100100];
map<ll,ll>phi;
ll euler(ll n)
{
    if(phi[n]!=0)return phi[n];
    ll i,res=n;
    ll temp=res;//传个参就不会TLE了???(迷
    for(i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            res=res/i*(i-1);
            while(n%i==0)
                n=n/i;
        }
    }
    if(n>1)res=res/n*(n-1);
    phi[temp]=res;//直接phi[n]会TLE
    return res;
}
ll PowerMod(ll a,ll b,ll c)
{
    ll ans=1;
    a=Mod(a,c);
    while(b>0)
    {
        if(b&1)
            ans=Mod(ans*a,c);
        b>>=1;
        a=Mod(a*a,c);
    }
    return ans;
}
ll solve(int l,int r,ll mod)
{
    if(l==r||mod==1)return Mod(a[l],mod);
    return PowerMod(a[l],solve(l+1,r,euler(mod)),mod);
}
int main()
{
    scanf("%d%lld",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    scanf("%d",&q);
    while(q--)
    {
        scanf("%d%d",&l,&r);
        printf("%lld\n",solve(l,r,m)%m);//记得这里还是要%m
    }
    return 0;
}

牛客练习赛22E

题意：

多了一个区间[l,r]加上x的操作，每次查询的模p也在改变(p <= 2e7)。

思路：

套个树状数组或者线段树都可以，这里要先线性筛出欧拉函数。

代码：

#define Mod(a,b) a<b?a:a%b+b
typedef long long ll;
int n;
#define MAXN 20000001
ll eu[MAXN];
ll pri[MAXN];
bool vis[MAXN];
void init()
{
    eu[1]=1;
    ll cnt=0;
    for(ll i=2;i<MAXN;i++)
    {
        if(!vis[i]){pri[cnt++]=i;eu[i]=i-1;}
        for(int j=0;j<cnt&&pri[j]*i<MAXN;j++)
        {
            vis[i*pri[j]]=1;
            if(i%pri[j]==0)
            {
                eu[i*pri[j]]=eu[i]*pri[j];
                break;
            }
            eu[i*pri[j]]=eu[i]*(pri[j]-1);
        }
    }
}
ll c[500010];
int lowbit(int x)
{
    return x&(-x);
}
ll query(int x)
{
    ll res=0;
    while(x)
    {
        res+=c[x];
        x-=lowbit(x);
    }
    return res;
}
void add(int x,ll v)
{
    while(x<=n)
    {
        c[x]+=v;
        x+=lowbit(x);
    }
}
ll PowerMod(ll a,ll b,ll c)
{
    ll ans=1;
    a=Mod(a,c);
    while(b>0)
    {
        if(b&1)
            ans=Mod(ans*a,c);
        b>>=1;
        a=Mod(a*a,c);
    }
    return ans;
}
ll solve(int l,int r,ll mod)
{
    if(l==r||mod==1)return Mod(query(l),mod);
    return PowerMod(query(l),solve(l+1,r,eu[mod]),mod);
}
int main()
{
    int l,r,q,op;
    ll m;
    init();
    scanf("%d%d",&n,&q);
    memset(c,0,sizeof(c));
    ll ls=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&m);
        add(i,m-ls);
        ls=m;
    }
    while(q--)
    {
        scanf("%d%d%d%lld",&op,&l,&r,&m);
        if(op==1)
        {
            add(l,m);
            add(r+1,-m);
        }
        else if(op==2)printf("%lld\n",solve(l,r,m)%m);
    }
    return 0;
}