这题是今年四川省赛的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;
}
分享到:
相关推荐
-基于 Python 的 Linux 应用防火墙(UESTC 课程设计)+源代码+文档说明- 小白不懂运行,下载完可以私聊问,可远程教学 该资源内项目源码是个人的课程设计,代码都测试ok,都是运行成功后才上传资源,答辩评审平均分...
1、资源内容:基于Matlab实现的卷积神经网络手写体识别 UESTC 深度学习导论选课期末作业 2、代码特点:内含运行结果,不会运行可私信,参数化编程、参数可方便更改、代码编程思路清晰、注释明细,都经过测试运行成功...
UESTC考研倒计时 可以记录考研倒计时
一个考研倒计时软件。。。 桌面上显示的,占用资源很小。。
uestc图书馆联网利器。您是否为图书馆无法联网而苦恼过,快来下载吧
uestc 的清水河上网脚本,大家可以参考下怎么写shell,写的不错
一份UESTC的ACM题目推荐,可以当作入门题来切
用于考研倒计时,也可用于其他的倒计时!!!
微信小程序源码-Cheese-UESTC-master 校内新闻大图版小程序
uestc微处理器体系结构嵌入式系统设计 计算机系统组成与体系结构PPT教案.pptx
课程项目 此仓库用以记录于 2018 - 2022 年,就读于电子科技大学软件工程(互联网“+”)专业,本科期间所写的课程作业代码及完成的实验报告。 关于 所有代码和实验报告仅作参考,请勿直接 copy!...
图论及应用-uestc
uestc_os_exp:UESTC操作系统实验
UESTC电子实验 大二下 复习PPT
uestc数字信号处理DSP答案 奥本海姆数字信号处理
电子科技大学研究生算法设计与分析课程的两次大作业和答案解析。目测肖明宇,董强老师的学生都管用
教学内容与要求 1掌握处理器在进程地址空间上的三种运行位置,了解内核编程不能使用C库函数和FPU,以及可能产生内存故障、核心栈溢出和四种内核竞争情形的原因。(2学时) 2熟悉进程描述符的组织,进程上下文和...
UESTC-计算机系统安全期末真题
UESTC矩阵随机复习资料.rar