主席树 ，线段树， zkw， 树状数组
卡常卡常卡常卡常

spfa水过！

这又没有k的取值范围，O(klogn)算法难道不是随便卡！？
所以说我们不应该使用O(nlognlogans)级别的二分答案吗？

卡ex_CRT，不卡CRT，什么鬼情况啊。。。

回复 @oi菜鸟 :
为啥

1L上榜留念~

啊好简单

半分块半bit，什么鬼玩意儿……

n个数相同时Gcd 可能> (R-L+1)*k,需特判,否则两数差<=(r-l+1),gcd<=(r-l+1);

困惑我半年之久的凸包......
终于过了.....
凸包第一道！

拉格朗日插值大法好，猜结论+插值……

一个log跑不过两个log系列

凸包首题。。。

額？就一個點？

最后需要处理一下重复的出现，否则不对，f[i][j]表示选取哪几个数（当前状态）余数为j，转移方程 f[i | (1<<k)][(j * 10 + s[k]) % d] += f[i][j]　　((i & (1<<k)) == 0) ，最后应输出f[1<<(len-1)][0]处理重复出现后的ans（排列数）

我不服，为什么Dijkstra这么慢

只分一次块，复杂度是O(n^(3/4))的吗？

我太弱了，打一下我的70分做法quq：
$ \sum_{i=1}^{n} \sum_{j=1}^{m} \phi(gcd(i, j)) $
$ = \sum_{d=1}^{n} \sum_{i=1}^{n} \sum_{j=1}^{m} \phi(gcd(i, j)) [gcd(i, j) == d]$
$ = \sum_{d=1}^{n} \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{m}{d} \rfloor} \phi(d*gcd(\frac{i}{d}, \frac{j}{d})) [gcd(\frac{i}{d}, \frac{j}{d}) == 1]$
$ = \sum_{d=1}^{n} \phi(d) \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{m}{d} \rfloor} [gcd(\frac{i}{d}, \frac{j}{d}) == 1]$
设$ F(n, m) = \sum_{i=1}^{n} \sum_{j=1}^{m} [gcd(i, j) == 1]$
则原式
$ = \sum_{d=1}^{n} \phi(d) F(\lfloor \frac{n}{d} \rfloor, \lfloor \frac{m}{d} \rfloor)$
F的计算参见 HAOI2011 问题B
分块优化，单次查询时间复杂度应该是接近O(n)的？
Orz

一开始没看见F(1) = 0。按一般的约数个数函数推了，后来发现了，一慌：读错题了，但是忽然想到F(1) = 0不过是把gcd == 1的贡献减去了而已。。。写一下推的过程：
设 $ D(x) = \sum_{d|x}^{ } 1 $ 也就是x的约数的个数。（与本题中F的区别就是$ D(1)=1 $)
$ \sum_{i=1}^{n} D(gcd(i, n)) = \sum_{d|n}^{ } \sum_{k=1}^{\lfloor \frac{n}{d} \rfloor} D(d) [gcd(k, \frac{n}{d}) == 1] $
$ = \sum_{d|n}^{ } D(d) * \sum_{k=1}^{\lfloor \frac{n}{d} \rfloor} [gcd(k, \frac{n}{d}) == 1] $
$ = \sum_{d|n} D(d) * \phi(\frac{n}{d})$
发现是个狄利克雷卷积的形式，我们先变换一下：(下面这个$ * $表示狄利克雷卷积运算)
$ = D * \phi$ = $ 1 * 1 * \phi$ = $ id * 1$
到这里求解就非常容易了，就是
$ = \sum_{d|n} \frac{n}{d} $
那原题里面不是D函数，而是F，区别在于$ F(1) = 0 $，怎么办
注意到原式子 $\sum_{i=1}^{n} F(gcd(i, n))$ ，我们求出来的是 $ \sum_{i=1}^{n} D(gcd(i, n))$，只有$ gcd(i, n) == 1 $ 的时候，F和D有偏差。
对于每一个$ gcd(i, n) == 1 $ ，我们都刚好多算了$ 1 $，所以最后我们答案多算了$ \phi(n) $，减去即可。
最终
$ Ans = \sum_{d|n} \frac{n}{d} - \phi(n) $
可以在$ O(\sqrt{n})$ 的时间复杂度内求解出来。

倒数第二个测试点什么鬼嘛.......
我选择打表.........
想着既然打表就打的爽快一点然后就借了@He 的快读.......
然后怎么就跑第一了........