回复 @scpointer :
膜拜神犇的代码，不过这个做法似乎还是会卡常

在这里表达我深深的歉意QAQ
毁了两个大神两节课QAQ
……

本题的难度应该不止一星，毕竟裸的剩余定理就3星（剩余定理3星其实也有点太高了……）。

回复 @Hzoi_AntiLeaf :
ysf大神完全可以写树套树主席树吗~~

回复 @紅蓮之心熾熱��_血瞳洞穿無盡陰暗 :
能用zkw过也是种技术
要不然我的zkw早过了......

真是醉了。。
这个题明明是考查我们各种数论的。。前6个点应该线段树维护区间乘积。
后4个点应该处理逆元（前6个点不行，因为p1和p2不一定与我们维护的数互质）
而且最后3个点由于p1与p2不是质数，所以必须用中国单身狗定理来处理逆元。。
然而，我最后一个点996242 个询问只有一个不对，一个啊！！！
当我打表过了以后，我点开另一个过了的大神的代码一看：天哪！
没有两个程序，没有逆元，没有中国单身狗定理，有的只是前6个点的做法：线段树维护区间乘积，但是，
但是这位大神居然用了ztw线段树然后+快读+快写+卡常卡过了！！！
真是跪了。。好好地一道数论题输给了常数，还不知道有一个询问是怎么错的。。
最后，希望大神帮我看看我那个询问为什么不对。。
好吧，我知道了，我开了三个数组存逆元（p2的三个因数），但我只把一个的下标为0的初始化为了1，又智障了。。

回复 @紅蓮之心熾熱��_血瞳洞穿無盡陰暗 :
那啥 我代码里不是zkw线段树
不是所有非递归的线段树处理的东西都是zkw线段树
虽然是卡常，这个做法还是讲道理的，我看来不比中国剩余定理做差
算法是这样的，首先对于线段树每个节点(flo,l,r)是第flo层的表示[l,r]区间的节点
设mid=(l+r)/2，a[]为输入的数组，记录下a[mid]一直往左边乘到a[l]的值，和a[mid+1]一直往右边乘到a[r]的值
这样对于一个询问的区间[gl,gr]只要找到一个区间[l,r]满足l<=gl<=mid<gr<=r就可以只做一次乘法就算出答案
整个算法乘法和取模的次数是严格(nlogn+m) 一共是2100万次
你可以数数你的扩展欧几里得和后面中国剩余定理的乘法和取模次数一共有多少次 这个常数完全赶得上一个log
(最后我有点好奇后面两位的代码和跑出来的时间是怎么过的

回复 @scpointer :
当然，无论什么做法，能过就是好算法，而且你的做法确实很有道理，这点我服，而且考试时当然是做法越简单越易实现越好，从这点看你的代码好得多。
我发评论只是为了宣泄下自己的痛苦，毕竟我太辣鸡了。。

回复 @Mike is Fool :
表示严重怀疑十多秒的是偷偷把时限放大过了再把时限改回去的。。

回复 @Mike is Fool :
你以为非递归线段树就能不T吗......

回复 @Mike is Fool :
最后四个点不是你卡常能过的，7要求逆元，8、9、10要用中国单身狗定理。。
别问我为什么，我都改了一下午了。。

这题非要我们把线段树写成非递归吗？卡常真严重。

回复 @scpointer :
原来是这样，吓到我了，还以为中午睡了一觉就会魔法了。。。

回复 @紅蓮之心熾熱��_血瞳洞穿無盡陰暗 : 上午的时候第六个点数据有问题，大概中午改了

令我心碎的神题。。干嚼我NOIP要滚粗了
什么鬼？上午70分的三个代码点重新评测（不是重新提交）就80了？！