回复 @cstring :
卧槽槽槽槽……忘了忘了……不要在意，我马上写= =
Update: spj已加入……我会说这题的spj比原题写着还麻烦？- - http://paste.ubuntu.com/10104855/

感觉测试数据和题目不符啊。。

感觉整个人都被反演了 #.#

一道好题，两种解法

张灵犀你弱爆了

泪流满面

C++中的STL库完全可以秒掉。。。
MAP+QUEUE+STRING

代码很简单，也就18行...

看起来挺难，弄明白题意后就非常简单了。其实就是在找一个元素的最终位置，如果该位置上没有其它元素，直接移过去；如果有其它元素，再对其进行相同的操作，或者将其移动到不会被占用的内存块上，直到所有元素都到达自己最终的位置。

咦？好奇怪啊……为什么筛F(n)的时候对素数定义$F(p) = mod + 1 - p$会挂但是定义成$F(p) = 1 - p$最后再判断正负就是对的？= =
呃我写一下推导过程吧，练练$\LaTeX{}$ ……
\begin{align}
Ans = & \sum_{a=1}^N \sum_{b=1}^M lcm(a, b) \\
=& \sum_{d=1}^{ \min(N, M)} \sum_{i=1}^{\lfloor {N/d} \rfloor} \sum_{j=1}^{\lfloor {M/d} \rfloor } [\gcd(i, j) = 1] i j d\\
= &\sum_{d=1}^{ \min(N, M)} \sum_{i=1}^{\lfloor {N/d} \rfloor} \sum_{j=1}^{\lfloor {M/d} \rfloor } \sum_{t | i \land t | j} \mu (t) i j d\\
考虑直接枚举t*d，&用i*d,j*d,\frac{td}{t}分别替换i, j, d；\\
Ans =& \sum_{td=1}^{ \min(N, M)} td \sum_{t | td} \mu (t) t \sum_{i=1}^{\lfloor {N/td} \rfloor } \sum_{j=1}^{\lfloor {M/td} \rfloor } i j \\
设F(n) = &\sum_{t | n} \mu (t) t ;\\
则Ans = & \sum_{td=1}^{ \min(N, M)} td F(td) \sum_{i=1}^{\lfloor {N/td} \rfloor } \sum_{j=1}^{\lfloor {M/td} \rfloor } i j
\end{align}
再来看F函数：
先直接用定义证明F是积性函数，然后直接套欧拉筛法：

 F[1] = 1;

 for(int i = 2;i <= Min;++i){

 if(!notp[i])prime[cnt++] = i, F[i] = 1 - i;

 for(int j = 0;j < cnt;++j){

 int t = i * prime[j];

 if(t > Min)break;

 notp[t] = true;

 if(i % prime[j] == 0){//miu(i * prime[j]) == 0

 F[t] = F[i];

 break;

 }

 F[t] = (LL)F[i] * F[prime[j]] % mod;

 }

 }

水到了这种地步，我也是醉了呀。。。看来NOIP（第一题）已经堕落了；；；；；

回复 @cstring :
是一种论文排版的工具

表示根本不会。。。。。

回复 @Asm.Def :
LATEX是什么。。。。

（【（】的答案为什么是（）【】（）【】 ？？？？明明加两个括号是最短的啊

我要掀桌子……

为什么我的莫队那么慢QAQ

。。为什么我每次退队之前都要判断是否队为空。。
不可能为空的啊。。。

我用的Floyd与邻接矩阵
醉了原来
cin>>x>>y>>G[x][y];不能写在一行啊！
自己的机子上跑的起来，测评各种RE
还有这个不能成环啊。

我这个SB竟然在用了O(n)线性筛的情况下，拼命把求ans优化到O(sqrt(n))