`
java-mans
  • 浏览: 11710404 次
文章分类
社区版块
存档分类
最新评论

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;
}


分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics