没出 $10^7$ 不想卡 OJ

陈年老代码果然该报废了，目测卡了内存......
不过说实话学了SA-IS之后就再也没写过了，但是现在回去看发现那套理论还蛮厉害的。

回复 @_Itachi :
用的 Menci 大佬的源，服务器渣，访问慢.....

话说SA-IS...诱导排序的后缀数组？

回复 @_Itachi :
强啊，倍增就过了.......，为什么不试试 $10^7$ 呢

回复 @_Itachi :
你需要buffer配合fwrite食用

回复 @Albert S. Chang :
noi 开了 O2

***，写错了两次快写（还是putchar版（捂脸）），感觉倍增的nlogn的log已经比它自带的大常数小了。。

对于楼上的代码我想提醒一句，template在没有O2的情况下速度清奇对于NOI系列这种死活都不给开优化开关的比赛还是少用的好...

哈哈，没用什么强大的读入输出，没有什么特殊的卡常姬巧，倍增小常数A掉

强啊，这是要普及一波sais的意思吗。。。

强啊

读入用/r 多亏看了评论。

给钢哥的前三个点跪了

我加了个特判。。。然后这么快的么。。。

自己写的好像不是标准的序列自动机，有大神可以Hack掉我的代码吗？

专门找了生活大爆炸看了看，才过........

对操作差分，即可把段修改变为两个点修改。
以时间为"版本号"建立可持久化线段树即可。

话说这道题用到并查集了么。。。。。

交一发惨WA最终发现是线性筛写错了。。
如何提高智商？
==== 分割线 ====
求$\sum_{i=1}^{n} \sum_{j=1}^{m} d(ij) $， $d(x)$ 为x的约数的个数。
假设$n<m$，不满足可以swap(n, m)不影响答案
首先 $d(nm) = \sum_{i|n} \sum_{j|m} [gcd(i,j) = 1]$
证明方法大致如下：
首先，若 $x = p_{1}^{k_{1}}p_{2}^{k_{2}}..p_{s}^{k_{s}}$
根据乘法原理则有$d(x) = (k_{1}+1)(k_{2}+1)...(k_{s}+1)$
考虑$d(nm)$，分解
$n = p_{1}^{a_{1}}p_{2}^{a_{2}}..p_{s}^{a_{s}}$ (指数可以为0，也就是不存在此因子)
$m = p_{1}^{b_{1}}p_{2}^{b_{2}}..p_{s}^{b_{s}}$ 
根据乘法原理
$d(nm) = (1+a_{1}+b_{1})(1+a_{2}+b_{2})..(1+a_{s}+b_{s})$
同时，我们容易发现，对于一个质因子$p_{k}$，并存在两个数u, v。使得
$gcd(u*p_{k}^{a_{k}}, v) = gcd(u*p_{k}^{a_{k}-1}, v) = .. = gcd(u, v) = ... = gcd(u, v*p_{k}^{b_{k}-1}) = gcd(u, v*p_{k}^{b_{k}}) = 1$ 共 $a_{k}+b_{k}+1$ 对这样的数对
那么总共有s个质因子，则 $\prod_{k=1}^{s} (a_{k}+b_{k}+1) $刚好等于$d(nm)$，证明完毕。 
所以
$ans = \sum_{i=1}^{n} \sum_{j=1}^{m} d(ij) $
$ = \sum_{i=1}^{n} \sum_{j=1}^{m} \sum_{i|n} \sum_{j|m} [gcd(i,j) = 1] $
$ = \sum_{i=1}^{n} \sum_{j=1}^{m} \lfloor \frac{n}{i} \rfloor \lfloor \frac{m}{j} \rfloor [gcd(i, j) = 1]$
$ = \sum_{d=1}^{n} \mu(d) (\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{m}{d} \rfloor} \lfloor \frac{n}{id} \rfloor \lfloor \frac{m}{jd} \rfloor) $
$ = \sum_{d=1}^{n} \mu(d) (\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \lfloor \frac{\lfloor \frac{n}{d} \rfloor}{i}\rfloor\sum_{j=1}^{\lfloor \frac{m}{d} \rfloor}\lfloor \frac{\lfloor \frac{m}{d} \rfloor}{j}\rfloor) $
于是发现$\sum_{ }^{ } \mu(d)$这部分可以分块优化，后面那部分呢?预处理 $d(n) = \sum_{i=1}^{n} \lfloor \frac{n}{i} \rfloor$就行了。。。
跑得还挺慢，5s多。%榜上dalao