UESTC 87 Easy Problem With Numbers

约定不等于承诺〃 2022-08-09 02:26 92阅读 0赞

### Description ###

Give a sequence of integers, you are required to deal with the following operations.

For each integer in the interval , change its value to previous value multiplying or dividing an integer .  
Output the remainder of the product of all the integers in interval mod a particular modulus.

### Input ###

First line of the input is a single integer T(1≤T≤15), indicating there are T test cases.

The first line of each test case contains two numbers N(1≤N≤10000)and M(1≤M≤109).

The second line contains N numbers, the initial values of A1,A2,...,AN(0≤Ai≤109).

The third line contains a single number Q(1≤Q≤10000).

Each of the next Q lines represents an operation.

“M L R x” means for each integer in the interval \[L, R\], changing its value to previous value multiplying an integer x, we guarantee that x is not exceeded 109 and non negative.

“D L R x” means for each integer in the interval \[L, R\], changing its value to previous value dividing an integer x, we guarantee that x is positive integer not exceeded 109 and all the integers in the interval \[L, R\] can be divided into x parts with no remainder.

“Q L R” means output the remainder of the product of the integer in interval \[L, R\] mod M.

For all the operations, we guarantee that L≤R and there is a blank line before each test case.

### Output ###

For each test case, print Case \#t: first, in which is the number of the test case starting from .

Then for each Q L R operation, output a single num in each line as the input says.

### Sample Input ###

5 6  
10 2 6 9 10  
5  
Q 1 2  
M 1 4 3  
Q 1 5  
D 1 3 2  
Q 1 3

### Sample Output ###

Case \#1:  
2  
0  
3

首先，我们明确一点，M并不一定是一个素数，所以直接关于M求逆元的做法是行不通的。  
那么可以想到的是分块乱搞，这样的复杂度估计是10000×10000−−−−−√=106。我猜肯定有人这么做，但是因为不太会乱搞，就只有想别的方法了。  
直接关于M求逆元的做法不行，是因为费马小定理求逆元要求的是素数，而另一个求逆元的工具，扩展欧几里得，要求的gcd(a,mod)==1，那么我们就可以想到将乘除的数都除尽关于M的质因子。

那么因为M是固定的，而且最多的质因子个数不超过13个，于是在线段树中存两个域值。  
一个是val：表示和M互质的数的乘积是多少；一个是tot\[i\]：表示M的第i个质因子在里面被乘了多少次。  
另外还有相应的懒标记。

于是就可以直接维护了。

// whn6325689
    // Mr.Phoebe
    // http://blog.csdn.net/u013007900
    #include <algorithm>
    #include <iostream>
    #include <iomanip>
    #include <cstring>
    #include <climits>
    #include <complex>
    #include <fstream>
    #include <cassert>
    #include <cstdio>
    #include <bitset>
    #include <vector>
    #include <deque>
    #include <queue>
    #include <stack>
    #include <ctime>
    #include <set>
    #include <map>
    #include <cmath>
    #include <functional>
    #include <numeric>
    #pragma comment(linker, "/STACK:1024000000,1024000000")
    
    
    using namespace std;
    #define eps 1e-9
    #define PI acos(-1.0)
    #define INF 0x3f3f3f3f
    #define LLINF 1LL<<50
    #define speed std::ios::sync_with_stdio(false);
    
    typedef long long ll;
    typedef unsigned long long ull;
    typedef long double ld;
    typedef pair<ll, ll> pll;
    typedef complex<ld> point;
    typedef pair<int, int> pii;
    typedef pair<pii, int> piii;
    typedef vector<int> vi;
    
    #define CLR(x,y) memset(x,y,sizeof(x))
    #define CPY(x,y) memcpy(x,y,sizeof(x))
    #define clr(a,x,size) memset(a,x,sizeof(a[0])*(size))
    #define cpy(a,x,size) memcpy(a,x,sizeof(a[0])*(size))
    #define debug(a) cout << #a" = " << (a) << endl;
    #define debugarry(a, n) for (int i = 0; i < (n); i++) { cout << #a"[" << i << "] = " << (a)[i] << endl; }
    
    #define mp(x,y) make_pair(x,y)
    #define pb(x) push_back(x)
    #define lowbit(x) (x&(-x))
    
    #define MID(x,y) (x+((y-x)>>1))
    #define getidx(l,r) (l+r | l!=r)
    #define ls getidx(l,mid)
    #define rs getidx(mid+1,r)
    #define lson l,mid
    #define rson mid+1,r
    
    template<class T>
    inline bool read(T &n)
    {
        T x = 0, tmp = 1;
        char c = getchar();
        while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
        if(c == EOF) return false;
        if(c == '-') c = getchar(), tmp = -1;
        while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
        n = x*tmp;
        return true;
    }
    template <class T>
    inline void write(T n)
    {
        if(n < 0)
        {
            putchar('-');
            n = -n;
        }
        int len = 0,data[20];
        while(n)
        {
            data[len++] = n%10;
            n /= 10;
        }
        if(!len) data[len++] = 0;
        while(len--) putchar(data[len]+48);
    }
    //-----------------------------------
    
    const int MAXN=100010;
    const int MAC=13;
    
    ll n,mod;
    int fac[MAC],cnt[MAC],tot;
    int a[MAXN];
    
    ll qpow(ll a,ll b)
    {
        if(b<0) return 0;
        ll res=1;
        a%=mod;
        while(b)
        {
            if(b&1) res=res*a%mod;
            b>>=1;
            a=a*a%mod;
        }
        return res;
    }
    
    ll exgcd(ll a,ll b,ll &d,ll &x,ll &y)
    {
        if(!b)
        {
            d=a,x=1,y=0;
        }
        else
        {
            exgcd(b,a%b,d,y,x);
            y-=x*(a/b);
        }
    }
    
    void init()
    {
        tot=0;
        int num=mod;
        for(int i=2; i*i<=num; i++)
        {
            if(num%i==0)
            {
                fac[tot++]=i;
                while(num%i==0) num/=i;
            }
        }
        if(num!=1)  fac[tot++]=num;
    }
    
    
    void change(int &x,int *cnt,int flag)
    {
        if(x==0)    return;
        for(int i=0; i<tot; i++)
        {
            if(x%fac[i]==0)
            {
                while(x%fac[i]==0)
                {
                    cnt[i]+=flag;
                    x/=fac[i];
                }
            }
        }
    }
    
    struct Node
    {
        int cnt[MAC],tot[MAC];
        ll mul,val;
        bool la;
        void init()
        {
            mul=val=1;
            la=0;
            CLR(cnt,0);
            CLR(tot,0);
        }
    } t[MAXN<<1];
    
    void pushup(int l,int r)
    {
        int idx=getidx(l,r),mid=MID(l,r);
        for(int i=0; i<tot; i++)
            t[idx].tot[i]=t[ls].tot[i]+t[rs].tot[i];
        t[idx].val=t[ls].val*t[rs].val%mod;
    }
    
    void pushdown(int l,int r)
    {
        int idx=getidx(l,r),mid=MID(l,r);
        if(!t[idx].la)  return;
        t[ls].la=t[rs].la=1;
        t[idx].la=0;
        ll &mul=t[idx].mul;
        t[ls].mul=t[ls].mul*mul%mod;
        t[rs].mul=t[rs].mul*mul%mod;
        t[ls].val=t[ls].val*qpow(mul,mid-l+1)%mod;
        t[rs].val=t[rs].val*qpow(mul,r-mid)%mod;
        mul=1;
        for(int i=0; i<tot; i++)
        {
            t[ls].tot[i]+=t[idx].cnt[i]*(mid-l+1);
            t[rs].tot[i]+=t[idx].cnt[i]*(r-mid);
            t[ls].cnt[i]+=t[idx].cnt[i];
            t[rs].cnt[i]+=t[idx].cnt[i];
            t[idx].cnt[i]=0;
        }
    }
    
    void build(int l,int r)
    {
        int idx=getidx(l,r),mid=MID(l,r);
        t[idx].init();
        if(l==r)
        {
            change(a[l],t[idx].tot,1);
            t[idx].val=a[l]%mod;
            return;
        }
        build(lson);
        build(rson);
        pushup(l,r);
    }
    
    void update(int l,int r,int L,int R,ll v)
    {
        int idx=getidx(l,r),mid=MID(l,r),len=r-l+1;
        if(L==l && r==R)
        {
            t[idx].mul=t[idx].mul*v%mod;
            t[idx].val=t[idx].val*qpow(v,len)%mod;
            t[idx].la=1;
            for(int i=0; i<tot; i++)
            {
                t[idx].cnt[i]+=cnt[i];
                t[idx].tot[i]+=cnt[i]*len;
            }
            return;
        }
        pushdown(l,r);
        if(L>mid)   update(mid+1,r,L,R,v);
        else if(R<=mid) update(l,mid,L,R,v);
        else
        {
            update(l,mid,L,mid,v);
            update(mid+1,r,mid+1,R,v);
        }
        pushup(l,r);
    }
    
    ll query(int l,int r,int L,int R)
    {
        int idx=getidx(l,r),mid=MID(l,r),len=r-l+1;
        if(L==l && r==R)
        {
            ll ret=t[idx].val;
            for(int i=0; i<tot; i++)
                ret=ret*qpow(fac[i],t[idx].tot[i])%mod;
            return ret;
        }
        pushdown(l,r);
        if(L>mid)   return query(mid+1,r,L,R);
        else if(R<=mid) return query(l,mid,L,R);
        else    return query(l,mid,L,mid)*query(mid+1,r,mid+1,R)%mod;
    }
    
    char op[11];
    
    int main()
    {
    //freopen("data.txt","r",stdin);
        int T,cas=1,q,x,y,z;
        scanf("%d",&T);
        while(T--)
        {
            scanf("%d %d",&n,&mod);
            for(int i=1; i<=n; i++)
                scanf("%d",&a[i]);
            init();
            build(1,n);
            printf("Case #%d:\n",cas++);
            scanf("%d",&q);
            while(q--)
            {
                scanf("%s",&op);
                if(op[0]=='Q')
                {
                    scanf("%d %d",&x,&y);
                    printf("%lld\n",query(1,n,x,y)%mod);
                }
                else if(op[0]=='M')
                {
                    scanf("%d %d %d",&x,&y,&z);
                    CLR(cnt,0);
                    change(z,cnt,1);
                    update(1,n,x,y,z);
                }
                else
                {
                    scanf("%d %d %d",&x,&y,&z);
                    CLR(cnt,0);
                    change(z,cnt,-1);
                    ll xx,yy,dd;
                    exgcd(z,mod,dd,xx,yy);
                    xx=(xx%mod+mod)%mod;
                    update(1,n,x,y,xx);
                }
            }
        }
        return 0;
    }