题面 传送门：洛咕 Solution 调到自闭，我好菜啊 为了方便讨论，以下式子$m>=n$ 为了方便书写，以下式子中的除号均为向下取整 我们来颓柿子吧qwq 显然，题目让我们求： $\large \sum_{i=1}^n\sum_{j=1}^m lcm(i,j)$ $lcm$没法玩，我们转到$gcd$形式： $\large \sum_{i=1}^n\sum_{j=1}^m \frac{i*j}{gcd(i,j)}$ 根据套路，我们去枚举$gcd$ $\large \sum_{i=1}^n\sum_{j=1…

题面 传送门：洛咕 Solution 我怎么只会刷水题 这题的双倍经验题，不多说啥了。 啥？范围不一样？ 那根据我们写数位DP及二维前缀和的经验，我们容斥一下...... 然后就没有然后了。 时间复杂度$O(m*\sqrt n)$ Code 人傻自带大常数,不开O2 T一个点 事实上这题可以把一些不必要的$longlong$改成$int$，刚好能过。可惜我太颓，不想改了 //Luogu P2522 [HAOI2011]Problem b //Jan,23rd,2019 //莫比乌斯函数双倍经验题 #include&…

题面： 传送门：洛咕 Solution 首先，我们需要一个结论： $\large d(i,j)=\sum_{x|i}\sum_{y|j}[gcd(x,y)=1]$ 证明 理性证明请看这篇博客的例五 本蒟蒻提供一个感性证明的方法：如果$x*y$是$i*j$的因数，我们必须有$x|i,y|j$，而后面那个$gcd(x,y)$是用来去重的 有了这个柿子之后，我们之后的推导就比较套路了： 为了方便讨论，之后的柿子均默认$m>n$ 为了方便书写，之后的除法默认向下取整 原式： $\large \sum_{i=…

题面 传送门：洛咕 Solution 这题比这题不懂简单到哪里去了 好吧，我们来颓柿子。 为了防止重名，以下所有柿子中的$x$既是题目中的$d$ 为了方便讨论，以下柿子均假设$b>=a$ 为了方便书写，以下除号均为向下取整 题目要求的显然是： $\large \sum_{i=1}^{a}\sum_{j=1}^{b}[gcd(i,j)=x]$ 根据套路，我们这里要先把这个$x$除掉 $\large \sum_{i=1}^{a/x}\sum_{j=1}^{b/x}[gcd(i,j)=1]$ 再根据套路，根据莫比乌斯函数…

题面 传送门：洛咕 Solution 推到自闭，我好菜啊 显然，这题让我们求： $\large \sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)\in prime]$ 根据套路，我们可以把判断是否为质数改为枚举这个质数，有： 为了方便枚举，我们在这里假设有$m>n$ $\large \sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{k\in prime}^{n}[gcd(i,j)= k]$ 显然，要让$gcd(i,j)=k$，必须要有$i,j$均为$k$的倍数，因此有： …