25题斩

被Int64和longlong卡出祥

咦？好奇怪啊……为什么筛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;

 }

 }

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

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

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

出题人你标程炸了(╯‵□′)╯︵┻━┻
数据已修复