ha

回复 @常可神牛 :
多谢常神牛的题解

手怎么这么贱。。。自己把方程推出来了能打错3次。。

PBDS大法好，只要35行即可AC。

回复 @Nil : 现在，要求你计算出和为素数共有多少种。他说的应该是“加起来是素数的情况有多少种”吧，而不是“加起来的素数有多少种”

初始化很重要，，跪了。。

回复 @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是什么。。。。