社区讨论

对于前缀积的取模问题

学术版参与者 4已保存回复 4

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@m43k8nj5
此快照首次捕获于
2024/11/30 10:35
去年
此快照最后确认于
2025/11/04 13:37
4 个月前
查看原帖
rt,如果我出了一道题叫做前缀积,给一个数组 aa,有 qq 次询问,每次问一个区间的乘积,但是这个乘积会很大,我想把它对一个数取模,那么怎么做?有没有可行的做法?
比如一个数组:
1, 4, 2, 3, 5
它的前缀积为:
1, 4, 8, 24, 120
那么求它的区间的乘积就是 ara_r 除以 al1a_{l-1}
那如果我想把结果对 10 取模:
它的前缀积为:
1, 4, 8, 4, 0
那么如何求它的区间的乘积?
如果 ara_r 能被 al1a_{l-1} 整除,如求 [2,3][2, 3] 的前缀积,那么答案就是 8/1=88/1=8
但如果不能被整除,或者除数为 00,怎么处理?
所以有没有可行的,快速的做法,谢谢

回复

4 条回复,欢迎继续交流。

正在加载回复...