题解 P3934 【Nephren Ruq Insania】

· · 题解

这个题的思路大佬们都介绍的差不多了，但是他们的代码真的好长，我介绍一种对于萌新很友好的代码。

前置知识：1. 扩展欧拉定理 a^k \equiv a^{k \% \varphi(p)+\varphi(p) } \ (mod \ p)(k>=\varphi(p))

注意扩展欧拉定理的使用条件是模数大于等于欧拉函数值

2.欧拉函数通项公式: \varphi(n)=n\prod\limits_{p|n,p\in prime}\frac{p-1}{p}

3.欧拉函数是积性函数: \varphi(nm)=\varphi(n)\varphi(m) \ (gcd(n,m)=1)

注意，\varphi 函数不是完全积性函数，互质才能乘起来哦；不互质的话不能乘起来。

#include<iostream>
#include<cstdio>
#include<map>
using namespace std; 
typedef long long ll;
ll tree[2000000];
ll n,m,p,prime[5000001],cnt,phi[20000001];
bool bj[20000001];
inline ll read(){//快读
    ll x=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
void eular()
{//线性筛欧拉函数 
    phi[1]=1;bj[1]=1;//特殊处理1的情况 
    for(register ll i=2;i<=20000000;i++)
    {
        if(!bj[i])//之前没被筛掉说明是指数 
        {
            prime[++cnt]=i;
            phi[i]=i-1;//质数和前面所有数互质，欧拉函数值位i-1
        }
        for(ll j=1;j<=cnt&&prime[j]*i<=20000000;j++)
        {//尝试用 prime[j]*i 去筛掉其他的数字 
            bj[prime[j]*i]=1;//是合数，标记上 
            if(i%prime[j]==0)//欧拉筛的核心思想：让一个数字只被它的最小质因子筛一次 
            {//prime是由小到大的，如果j不是i的最小质因子，那么i应该会在之前就break了 
            //之后就不用再拿i去筛了，因为下次筛到的数的最小质因子一定是i的最小质因子 
                phi[i*prime[j]]=phi[i]*prime[j];
                break;//欧拉函数的通项公式，注意这里不是积性函数部分，i已经包含prime[j],i*prime[j]的phi就是比i的prime[j]倍 
            }
            phi[i*prime[j]]=phi[i]*phi[prime[j]];//i,prime[j]互质，利用phi的积性乘起来就好了 
        }
    }
}//区间加、查询单点，使用简短的树状数组维护
ll lowbit(ll x){return (x&(-x));
void updata(ll x,ll cost){
    while(x<=n){
        tree[x]+=cost;
        x+=lowbit(x);
    }//把x位加上cost
}
ll query(ll x){//查询tree数组的前缀和1-x
    ll ans=0;
    while(x>0){
        ans+=tree[x];
        x-=lowbit(x);
    }
    return ans;
}
ll fastpow(ll di,ll zhi,ll p)
{
    ll flag=0,yu=1;
    if(di>=p)flag=1,di%=p;//小心，去掉这句60分，否则如果有0次方的情况就去世了 
    //数据本身不会出现0次方的情况，但是别忘了我们的fastpow是取过模的，谁知道会不会有0 
    while(zhi>0)
    {
        if(zhi%2==1)yu=yu*di;
        di=di*di;//这里和普通的快速幂不同 ，先不要对di和yu取模，
        //因为扩展欧拉定理的使用需要指数大于模数的欧拉函数值，而在我们递归调用solve的时候
        //fastpow()就是上一层solve的指数！（它的p是上一层的欧拉函数值）所以要判断是否能达到p。 
        if(yu>=p)flag=1,yu%=p;//如果达到了p就标记
        if(di>=p)flag=1,di%=p;
        zhi=zhi/2;
    }
    if(flag)yu+=p;//如果到达p，根据扩展欧拉定理加上p 
    return yu;
}
//看似是最坏O（n）的dfs，其实最多执行log层
//对一个数字不停求欧拉函数，求logn次就会变成1
//例如phi(100)->phi(40)->phi(16)->phi(8)->phi(4)-phi>(2)->1
//因为gcd(i,n)=gcd(n-i,n),任意n>2,phi(n)为偶数 
//偶数一定含有素因子2，根据欧拉函数通项公式，可以发现每次求欧拉函数都是至少折半的
//扩展欧拉定理，不知道的建议取做 欧拉定理 那个题目 
ll Query(ll l,ll r,ll p)
{//做这个题目还可以顺手切了Power Tower，把树状数组改成正常数组就好了 
    ll now=query(l);
    if(l==r||p==1)return now>=p?now%p+p:now;//注意边界有两个：p已经降到了1或者序列已经取完，还是判断w[l]和p的大小关系 
    return fastpow(now,Query(l+1,r,phi[p]),p); //递归调用solve，注意不要取余数，这可能会导致fastpow里最后加上的p白加了 
}
int main()
{
    eular();
    n=read();m=read();
    for(ll i=1;i<=n;i++)
    {
        ll x=read();
        updata(i,x);//维护差分原数组的差分,修改一个区间值只会影响l、r+1的差分值
        //这样query求出的tree的前缀和就是单点值，实现了区间加、求单点 
        updata(i+1,-x);
    }
    for(ll i=1;i<=m;i++)
    {
        ll opt,x,y,z;
        opt=read();x=read();y=read();z=read();
        if(opt==1)
        {
            updata(x,z);//维护差分序列 
            updata(y+1,-z);
        }
        else printf("%lld\n",Query(x,y,z)%z);//注意这里还要%p，因为fastpow()最后一次执行的时候可能加上了P，而solve里是不能取余数的 
    }
    return 0;
}