牛客 指数循环节

题目描述

请注意每次的模数不同。

输入描述:

第一行两个整数 n,m 表示序列长度和操作数

接下来一行，n个整数，表示这个序列

接下来m行，可能是以下两种操作之一：

操作1：区间[l,r]加上 x

操作2：查询区间[l,r]的那个式子mod p的值

输出描述:

对于每个询问，输出一个数表示答案

示例1

输入

复制

6 4
1 2 3 4 5 6
2 1 2 10000007
2 2 3 5
1 1 4 1
2 2 4 10

输出

复制

1
3
1

备注:

n , m <= 500000

序列中每个数在 [1,2e9] 内，x <= 2e9 , p <= 2e7

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<set>
#define mem(a,x) memset(a,x,sizeof(a))
#define s1(x) scanf("%d",&x)
#define s2(x,y) scanf("%d%d",&x,&y)
#define s3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define s4(x,y,z,k) scanf("%d%d%d%d",&x,&y,&z,&k)
#define ff(a,n) for(int i = 0 ; i < n; i++) scanf("%d",a+i)
#define tp(x) printf("x = %d\n",x)
#define ansp(x) printf("%d\n",x)
#define ls 2*rt
#define rs 2*rt+1
#define lson ls,L,mid
#define rson rs,mid+1,R
#define ll long long
using namespace std;
typedef pair<int,int> pii;
const ll inf = 0x3f3f3f3f;

const int mx =5e5+10;
const int P =2e7+10;
int n,m,num[mx],phi[P],pri[P/10];
ll c[mx];
bool isp[P];


inline ll lowbit(int x){return x&(-x);}
inline ll ask(int x){ll res=0;while(x)res+=c[x],x-=lowbit(x);return res;}
inline void add(int x,int d){while(x<=n)c[x]+=d,x+=lowbit(x);}


void init(int n)
{
    int p=0;
    for(int i=2;i<=n;i++)
    {
        if(isp[i]==0)  pri[++p]=i,phi[i]=i-1;
        for(int j=1;j<=p&&i*pri[j]<=n;j++)
        {
            isp[i*pri[j]]=1;
            if(i%pri[j]==0)
            {
                phi[i*pri[j]]=phi[i]*pri[j];
                break;
            }
            else phi[i*pri[j]]=phi[i]*(pri[j]-1);
        }
    }
}

inline ll fmod(ll x, int p){       //如果这里写了ll p 的话， F函数那里传过来的也要ll
    if(x >= p)
        return x%p+p;
    return x;
}
ll powmod(ll a,ll b,int p){       //参数int 和 ll 不要混用，会出事，即使是int 传ll
    ll ans = 1;
    a = fmod(a,p);
    while(b){
        if(b%2){
            ans *= a;
            ans = fmod(ans,p);
        }
        b /= 2;
        a = a*a;
        a = fmod(a,p); 
    }
    return ans;
}
ll F(int l, int r,  int p){
    ll te = ask(l);
    if(l == r|| p==1)
        return fmod(te,p);
    return powmod(te,F(l+1,r,phi[p]),p);
} 
int main(){
    //int T=10; scanf("%d",&T);
    //  freopen("F:\\in.txt","r",stdin);
    
    init(2e7+2);
    
//  cout<<"打表结束"<<endl; 
    s2(n,m);
    for(int i = 1; i <= n; i++){
        s1(num[i]);
        add(i,num[i]-num[i-1]);
    }
    while(m--){
        int cmd,a,b,p;
        s4(cmd,a,b,p);
    //  cin>>cmd>>a>>b>>p;
        if(cmd == 1){
            add(a,p);
            add(b+1,-p);
        }
        else{
            printf("%lld\n",F(a,b,p)%p);
        }
    }


    return 0;
}

模板

#include<bits/stdc++.h>
 
#define ll long long
using namespace std;
const int N=500000+10;
const int P=2e7+10;
ll c[N];bool isp[P];int pri[P/10];int phi[P];ll a[N];
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
struct ios {
    inline char read(){
        static const int IN_LEN=1<<18|1;
        static char buf[IN_LEN],*s,*t;
        return (s==t)&&(t=(s=buf)+fread(buf,1,IN_LEN,stdin)),s==t?-1:*s++;
    }
  
    template <typename _Tp> inline ios & operator >> (_Tp&x){
        static char c11,boo;
        for(c11=read(),boo=0;!isdigit(c11);c11=read()){
            if(c11==-1)return *this;
            boo|=c11=='-';
        }
        for(x=0;isdigit(c11);c11=read())x=x*10+(c11^'0');
        boo&&(x=-x);
        return *this;
    }
}io;
 
/*
inline int lowbit(int x){return x&(-x);}
ll ask(int x){ll res=0;while(x)res+=c[x],x-=lowbit(x);return res;}
inline void add(int x,ll d,int n){while(x<=n)c[x]+=d,x+=lowbit(x);}
*/
inline int lowbit(int x){return x&(-x);}
ll ask(int x){
    ll res=0;
    for (;x>0;x-=lowbit(x)) res+=c[x];
    return res;
}
inline void add(int x,ll v,int n){
    for (;x<=n;x+=lowbit(x)) c[x]+=v;
}
 
 
void init(int n)
{
    int p=0;
    for(int i=2;i<=n;i++)
    {
        if(isp[i]==0)  pri[++p]=i,phi[i]=i-1;
        for(int j=1;j<=p&&i*pri[j]<=n;j++)
        {
            isp[i*pri[j]]=1;
            if(i%pri[j]==0)
            {
                phi[i*pri[j]]=phi[i]*pri[j];
                break;
            }
            else phi[i*pri[j]]=phi[i]*(pri[j]-1);
        }
    }
}
 
 
int Mod(ll x, int y) { return x >= y ? (x % y + y) : x; }//????
  
inline int qmod(ll x, int n, int p) {
    ll ans = 1;
    x = Mod(x, p);
    for( ; n; n >>= 1) {
        if(n & 1) ans = Mod(ans * x, p);
        x = Mod(x * x, p);
    }
    return ans;
}
int dfs(int l, int r, int p)
{
    ll val = ask(l);
    if(l == r || p == 1) return Mod(val, p);    //降幂加速
    return qmod(val, dfs(l + 1, r, phi[p]), p);
}
 
int main()
{
    //cout<<qmod(2,3,5);
    int n,q;io>>n>>q;
    for(int i=1;i<=n;i++)io>>a[i],add(i,a[i]-a[i-1],n);
    ll a,b,c,d;
    init(20000005);
    while(q--)
    {
        io>>a>>b>>c>>d;
        //a=read();b=read();c=read();d=read();
        if(a==1)add(b,d,n),add(c+1,-d,n);
        else printf("%d\n",dfs(b,c,d)%d);
    }
}