UESTC 1712 Easy Problem With Numbers 线段树+扩展欧几里得求逆元

这题是今年四川省赛的E题， 如果懂逆元的话很容易想到做法，不懂的话就像我似的 沙茶了。

四处求许久，求得神牛代码一份，思路一份，写了许久后最终得以A掉此题。

题意就不再说了，如果你知道product是乘积的意思的话这题就不难理解

附上神牛原版思路：

如果这个题只有乘法，那么你肯定会做吧？线段树更新区间查找区间。

那么有除法呢？当一个数x和m互质的时候，除以x可以改为乘以x的逆元。（至于互质的数求逆元用扩展欧几里德，这个网上可以随便找到）

但是这题并不能保证除的数与m互质吧？什么时候x与m不互质呢？就是x与m含有公因子吧？

那么我们一开始就把m分解，分解出来m有p1,p2,p3,p4...pn等一些因子。

那么在这个题里面，每个数x都可以表示成p1^c1*p2^c2*p3^c3.....*pn^cn*A。这里A就是x去掉p1,p2,p3.。。等因子后的数，A与m就不含公因子了吧，就可以换成A与m的逆元。线段树里面呢，就维护c1,c2,c3.....和A的值。乘或除的时候c1,c2.。。就相应加或减。A就直接乘逆元就行了。其实就是一个线段树懒操作了，更新区间查找区间。

然后附上本沙茶的代码， 刚开始自己写各种细节问题啊，TLE,WA数不胜数，最后拿神牛的代码对拍才发现问题

这里解释一下代码：

MOD就是题目中所说的M

fac数组存的是MOD的质因子们，cnt就是这个数组的大小了

xnum数组是一个中间数组，每次更新的时候都会乘以或者除以一个数，那么xnum数组就是存储这个数中与MOD相关的因子的个数

a数组就是一个读入数据的数组

num数组存储的是某个区间上与MOD相关每个因子分别的个数的总和

pernum主要用于lazy操作，主要用于维护每个结点上各个与MOD相关因子的个数

cover就是覆盖标记了，也是用于lazy操作

multi也是用于lazy操作，表示某个区间所有的点都乘以某个数

val就是某个区间所有值相乘%MOD的结果

然后就是函数了:

Exgcd是用来求解线性方程的，当然也是用来求逆元的，注意gcd(a, b)应当等于1

powmod 函数就是快速幂取模了，注意b为负数的情况。这个情况是某结点值为0时可能发生的情况，0不包含任何因子，但可以除以任何因子，造成了因子个数减去的时候变成了负数。

factor函数是用来算中间数组xnum的

然后说一下逆元那部分 我的拙见

对于a/b mod c

如果gcd(b, c) = 1

那么必存在bx +cy = 1

然后a*x mod c = a/b * bx mod c = a/b *(1 - cy) mod c = a/b mod c - a/b * cy mod c

而 a/b * cy mod c = 0 所以 a*x mod c = a / b mod c

那么可以用欧几里得去求逆元x, 然后a*x mod c 与刚才的式子等价，特别当c为质数的时候，可以直接取逆元为b ^（c - 2 )% c即可

但是如果b,c不互质呢 gcd(b, c)不为1,

又说a%b=0，那么很显然a中必然有因子为gcd(b, c) ，约分后，b,c将互质，又可以求了

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#define MAXN 11111
#define MAXM 55
#define lch(x) x<<1
#define rch(x) x<<1|1
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
using namespace std;
typedef long long ll;
int fac[11];
int cnt, n, MOD;
int xnum[11];
int a[MAXN];
int num[4 * MAXN][11], pernum[4 * MAXN][11];
int cover[4 * MAXN];
ll multi[4 * MAXN];
ll val[4 * MAXN];
ll ExGcd(ll a, ll b, ll &x, ll &y)
{
    if(b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    ll r = ExGcd(b, a % b, x, y);
    ll t = x;
    x = y;
    y = t - a / b * y;
    return r;
}
ll PowMod(ll a, ll b, ll c)//a^b mod c
{
    if(b < 0) return 0;
      ll ret = 1;
      a %= c;
      for (; b; b >>= 1, a = (a * a) % c)
            if (b & 1)
                  ret = (ret * a) % c;
      return ret;
}
void Factor(int &x, int v)
{
    for(int i = 0; i < cnt; i++)
    {
        xnum[i] = 0;
        if(x % fac[i] == 0)
        {
            while(x && x % fac[i] == 0)
            {
                x /= fac[i];
                xnum[i] += v;
            }
        }
    }
}
void PushUp(int rt)
{
    for(int i = 0; i < cnt; i++) num[rt][i] = num[lch(rt)][i] + num[rch(rt)][i];
    val[rt] = val[lch(rt)] * val[rch(rt)] % MOD;
}
void PushDown(int l, int r, int rt)
{
    if(cover[rt])
    {
         int mid = (l + r) >> 1;
         int llen = mid - l + 1;
         int rlen = r - mid;
         multi[lch(rt)] = multi[lch(rt)] * multi[rt] % MOD;
         multi[rch(rt)] = multi[rch(rt)] * multi[rt] % MOD;
         val[lch(rt)] = val[lch(rt)] * PowMod(multi[rt], llen, MOD) % MOD;
         val[rch(rt)] = val[rch(rt)] * PowMod(multi[rt], rlen, MOD) % MOD;
         cover[lch(rt)] = cover[rch(rt)] = cover[rt];
         cover[rt] = 0;
         multi[rt] = 1;
         for(int i = 0; i < cnt; i++)
         {
             num[lch(rt)][i] += pernum[rt][i] * llen;
             num[rch(rt)][i] += pernum[rt][i] * rlen;
             pernum[lch(rt)][i] += pernum[rt][i];
             pernum[rch(rt)][i] += pernum[rt][i];
             pernum[rt][i] = 0;
         }
    }
}
void Build(int l, int r, int rt)
{
    cover[rt] = 0;
    multi[rt] = 1;
    for(int i = 0; i < cnt; i++) pernum[rt][i] = 0;
    if(l == r)
    {
        Factor(a[l], 1);
        for(int i = 0; i < cnt; i++) num[rt][i] = xnum[i];
        val[rt] = a[l] % MOD;
        return;
    }
    int m = (l + r) >> 1;
    Build(lson);
    Build(rson);
    PushUp(rt);
}
void update(int L, int R, ll c, int l, int r, int rt)
{
    if(L <= l && R >= r)
    {
        int len = r - l + 1;
        val[rt] = val[rt] * PowMod(c, len, MOD) % MOD;
        multi[rt] = multi[rt] * c % MOD;
        cover[rt] = 1;
        for(int i = 0; i < cnt; i++)
        {
            num[rt][i] += xnum[i] * len;
            pernum[rt][i] += xnum[i];
        }
        return;
    }
    int m = (l + r) >> 1;
    PushDown(l, r, rt);
    if(L <= m) update(L, R, c, lson);
    if(R > m) update(L, R, c, rson);
    PushUp(rt);
}
ll query(int L, int R, int l, int r, int rt)
{
    if(L <= l && R >= r)
    {
        ll t = val[rt];
        for(int i = 0; i < cnt; i++) t = t * PowMod(fac[i], num[rt][i], MOD) % MOD;
        return t;
    }
    int m = (l + r) >> 1;
    PushDown(l, r, rt);
    ll t = 1;
    if(L <= m) t = t * query(L, R, lson) % MOD;
    if(R > m) t = t * query(L, R, rson) % MOD;
    return t;
}
int main()
{
    int T, cas = 0;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d", &n, &MOD);
        cnt = 0;
        int temp = MOD;
        for(int i = 2; i * i <= temp; i++)
            if(temp % i == 0)
            {
                fac[cnt++] = i;
                while(temp % i == 0) temp /= i;
            }
        if(temp != 1) fac[cnt++] = temp;
        for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
        Build(1, n, 1);
        int q, x, y, z;
        char s[5];
        scanf("%d", &q);
        printf("Case #%d:\n", ++cas);
        while(q--)
        {
            scanf("%s", s);
            if(s[0] == 'M')
            {
                scanf("%d%d%d", &x, &y, &z);
                Factor(z, 1);
                update(x, y, z, 1, n, 1);
            }
            else if(s[0] == 'D')
            {
                scanf("%d%d%d", &x, &y, &z);
                Factor(z, -1);
                ll px, py;
                ExGcd(z, MOD, px, py);
                px %= MOD;
                if(px < 0) px += MOD;//逆元求出后要防止是负数
                update(x, y, px, 1, n, 1);
            }
            else if(s[0] == 'Q')
            {
                scanf("%d%d", &x, &y);
                printf("%lld\n", query(x, y, 1, n, 1) % MOD);
            }
        }
    }
    return 0;
}