代码很简单，也就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))

bzoj数据略水。。有个很大的错误都A了。。

检查起来整个人都不好

我更懒，写的分块。。。。。。

建议发题者改一下，最后一组数据多组数据输入

神奇的莫队算法……（话说标准的莫队算法写的都是Manhattan MST?好吧我偷懒写的是更弱的Manhattan Distance下的Hamilton Path近似解……不过对于随机数据比写矬了的MST还快一点……）
分块的时候其实可以不用显式地储存每块的坐标范围……只要每扫够B格排序一次即可。
顺便还有这样一个小小的细节……考虑二维坐标系中的一个最小曼哈顿距离哈密尔顿路径的近似解，如果在当前块中我们走到了最靠上的一个点，那么在走下一块的时候明显是从上往下走更优>_<所以我就写了一对y轴的比较函数，交替使用……

bool cmp2(const Query &a, const Query &b){return a.R < b.R;}

bool cmp3(const Query &a, const Query &b){return a.R > b.R;}

typedef bool(*CMP_FUNC)(const Query &, const Query &);

CMP_FUNC func[2] = {cmp2, cmp3};

为什么开优化开关过补了！不干QAQ！

数据给的非常好，就是题目中没有给出提示。这道整整弄了一天，收获很多，但发现都是些基础的东西，看来平时还得注意基础。
还有就是lis的nlogn算法好写，这道题关键是如何保存路径