这题是今年四川省赛的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;
}
分享到:
相关推荐
### 线段树题目详解 #### 1. 线段覆盖问题 - **ZOJ 1610** 和 **POJ 2777**:这两道题都是典型的线段覆盖问题,需要利用线段树来解决。基本思路是通过线段树维护每个区间是否被覆盖的状态。对于每个覆盖请求,更新...
-基于 Python 的 Linux 应用防火墙(UESTC 课程设计)+源代码+文档说明- 小白不懂运行,下载完可以私聊问,可远程教学 该资源内项目源码是个人的课程设计,代码都测试ok,都是运行成功后才上传资源,答辩评审平均分...
《UESTC考研倒计时V2.00:高效备考的智能助手》 在繁忙而紧张的考研复习过程中,时间管理至关重要。"UESTC考研倒计时V2.00"是一款专为备考学子设计的桌面应用,它以其小巧的体积、高效的性能,成为众多考生的得力...
1、资源内容:基于Matlab实现的卷积神经网络手写体识别 UESTC 深度学习导论选课期末作业 2、代码特点:内含运行结果,不会运行可私信,参数化编程、参数可方便更改、代码编程思路清晰、注释明细,都经过测试运行成功...
适合研究生FPGA课程-数据异步复接设计-设计报告
从最短路、最小生成树到最大流,从并查集、快速查找再到数论、线段树,每个类别都包含了至少几个题目,覆盖了算法的多个层面。这些题目不仅考验着对特定算法的理解,也要求学习者具备将理论应用于实际问题的能力。 ...
【UESTC考研倒计时】是一款专为准备西南交通大学(UESTC)考研的学生设计的应用程序。这款工具的主要功能是帮助考生有效地追踪并管理他们的备考时间,确保他们能在考试来临前充分准备。 考研,即全国硕士研究生统一...
uestc图书馆联网利器。您是否为图书馆无法联网而苦恼过,快来下载吧
uestc 的清水河上网脚本,大家可以参考下怎么写shell,写的不错
【UESTC考研倒计时+V2[1][1].00(大工版)】是一款专为考研学子设计的倒计时应用,其主要功能是帮助用户追踪距离考研的剩余时间,以此来规划和调整自己的复习进度。该应用不仅限于考研倒计时,还可以适用于其他需要倒...
课程项目 此仓库用以记录于 2018 - 2022 年,就读于电子科技大学软件工程(互联网“+”)专业,本科期间所写的课程作业代码及完成的实验报告。 关于 所有代码和实验报告仅作参考,请勿直接 copy!...
《算法设计与分析:UESTC课程深度探讨》 在信息技术高速发展的今天,算法设计与分析已经成为计算机科学领域不可或缺的一部分。电子科技大学(UESTC)作为国内知名的高等学府,在研究生教育阶段,特别注重培养学生的...
"Cheese-UESTC-master" 是一个针对校内新闻大图展示的小程序项目,它专为UESTC(电子科技大学)设计,允许用户方便地查看和浏览学校内的最新新闻资讯。 该项目的源码结构通常包含以下几个关键部分: 1. **app.js**...
图论及应用-uestc
uestc_os_exp:UESTC操作系统实验
基于UESTC-FPGA的异步时钟域数据复用设计源码+全部资料齐全.zip基于UESTC-FPGA的异步时钟域数据复用设计源码+全部资料齐全.zip 【备注】 1、该项目是高分课程设计项目源码,已获导师指导认可通过,答辩评审分达到95...
UESTC电子实验 大二下 复习PPT
"uestc微处理器体系结构嵌入式系统设计 计算机系统组成与体系结构PPT教案" 本资源是关于微处理器体系结构嵌入式系统设计和计算机系统组成与体系结构的PPT教案,共64页。以下是从该资源中生成的相关知识点: 1. ...
电子科技大学(UESTC)_成电学子每日体温自动填报_uestc_temperature_report