回复 @紅蓮之心熾熱��_血瞳洞穿無盡陰暗 :
那啥 我代码里不是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吗......

说好的常数级修改，结果改的连数据范围都不能信了

25行，懒到不优化。。。。。。

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

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

回复 @Rapiz :
这个可以保证。相当于是对于以每个点为起点进行最短路，在过程中中途终止，记录下答案，然后继续进行。
如果说你能卡掉的话，给我一组数据。

数据有误，数据中询问有最大路径 d等于1e9+1
如果把没有的边权值设为1e9+1就能A
设成更大的就过不去了
8,9,10组应该都有问题，第8组 921161个询问对应最大值就是1e9+1，答案输出了96（所有的点），正确应该是88

最大值请赋1e9+1……
0x3f调了一天

小于！小于！小于！

不会爆栈，这很不科学

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

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

我真是作啊，，，，，，

啊啊啊，我要报警啦