比较简单的一道推式子的题。(清华集训居然会出这种水题的吗)
题目链接
题意概述
[\sum_{i=1}^{n} \sum_{j=1}^{m} (n \bmod i) \times (m \bmod j), i \neq j ]
(\mod 19940417) 的值
思路分析
直接容斥一下然后推式子即可，见下：
[\begin{aligned}\sum \limits_{i=1}^n \sum \limits_{j=1}^m(n\bmod i)(m\bmod j) &=\sum \limits_{i=1}^n (n \bmod i)\sum \limits_{j=1}^m (m \bmod j)-\sum \limits_{i=1}^{\min(n,m)} (n\bmod i)(m \bmod j)\ &=\sum \limits_{i=1}^n (n \bmod i) \sum \limits_{j=1}^m (m-\left\lfloor\dfrac{m}{j}\right\rfloor \times j)-\sum \limits_{i=1}^{\min(n,m)}(n-\left\lfloor\dfrac{n}{i}\right\rfloor\times i)(m-\left\lfloor\dfrac{m}{i}\right\rfloor\times i)\ &=\sum \limits_{i=1}^n (n \bmod i) (\sum \limits_{j=1}^mm -\sum \limits_{j=1}^m\left\lfloor\dfrac{m}{j}\right\rfloor \times j)-\sum \limits_{i=1}^{\min(n,m)}(nm-n\left\lfloor\dfrac{m}{i}\right\rfloor\times i-m\left\lfloor\dfrac{n}{i}\right\rfloor\times i+\left\lfloor\dfrac{m}{i}\right\rfloor\left\lfloor\dfrac{n}{i}\right\rfloor\times i^2)\ &=\sum \limits_{i=1}^n (n \bmod i)(m^2-\sum \limits_{j=1}^m\left\lfloor\dfrac{m}{j}\right\rfloor \times j)-\sum \limits_{i=1}^{\min(n,m)}nm+n\sum \limits_{i=1}^{\min(n,m)}\left\lfloor\dfrac{m}{i}\right\rfloor \times i+m\sum \limits_{i=1}^{\min(n,m)}\left\lfloor\dfrac{n}{i}\right\rfloor \times i-\sum\limits_{i=1}^{\min(n,m)}\left\lfloor\dfrac{n}{i}\right\rfloor \left\lfloor\dfrac{m}{i}\right\rfloor \times i^2\ &=(m^2-\sum \limits_{j=1}^m\left\lfloor\dfrac{m}{j}\right\rfloor \times j)\sum \limits_{i=1}^n (n\bmod i)-\min(n,m)nm+n\sum \limits_{i=1}^{\min(n,m)}\left\lfloor\dfrac{m}{i}\right\rfloor \times i+m\sum \limits_{i=1}^{\min(n,m)}\left\lfloor\dfrac{n}{i}\right\rfloor \times i-\sum\limits_{i=1}^{\min(n,m)}\left\lfloor\dfrac{n}{i}\right\rfloor \left\lfloor\dfrac{m}{i}\right\rfloor \times i^2\ &=(m^2-\sum \limits_{j=1}^m\left\lfloor\dfrac{m}{j}\right\rfloor \times j)(n^2-\sum \limits_{i=1}^n\left\lfloor\dfrac{n}{i}\right\rfloor\times i)-\min(n,m)nm+n\sum \limits_{i=1}^{\min(n,m)}\left\lfloor\dfrac{m}{i}\right\rfloor \times i+m\sum \limits_{i=1}^{\min(n,m)}\left\lfloor\dfrac{n}{i}\right\rfloor \times i-\sum\limits_{i=1}^{\min(n,m)}\left\lfloor\dfrac{n}{i}\right\rfloor \left\lfloor\dfrac{m}{i}\right\rfloor \times i^2\ \end{aligned} ]
发现前四项都可以 整除分块随便求。
我们考虑最后一项怎么求。
首先考虑 (\sum\limits_{i=1}^{\min(n,m)}\left\lfloor\dfrac{n}{i}\right\rfloor \left\lfloor\dfrac{m}{i}\right\rfloor)，这实际上也可以整除分块，只不过需要 二维整除分块。
其实它和一般的整除分块区别也不大，很显然，每次只需要改一下块长就好了。
具体地，每次求 (r) 时：
[r=\min(\left\lfloor\dfrac{n}{\left\lfloor \dfrac{n}{l}\right\rfloor}\right\rfloor,\left\lfloor\dfrac{m}{\left\lfloor \dfrac{m}{l}\right\rfloor}\right\rfloor) ]
时间复杂度是 (O(\sqrt \min(n,m)))。
然后考虑 (\sum \limits_{i=1}^{\min(n,m)} i^2) 怎么求。
有一个结论：
[1^2+2^2+3^2+\cdots+n^2=\dfrac{n(n+1)(2n+1)}{6} ]
所以我们就可以求出整个的式子了。
易错点
(19940417) 不是素数，所以请注意：
模意义下计算(x) 的逆元只有当(\bmod) 为素数时才能使用(qpow(x,mod-2)) ！！！
模意义下计算(x) 的逆元只有当(\bmod) 为素数时才能使用(qpow(x,mod-2)) ！！！
模意义下计算(x) 的逆元只有当(\bmod) 为素数时才能使用(qpow(x,mod-2)) ！！！
我是不会告诉你我在这挂了一个小时的……
所以可以使用 exgcd 预处理出来 (2) 和 (6) 的逆元，然后求解。
代码实现
//luoguP2260
#include
#include
#include
#define int long long
using namespace std;
const int mod=19940417,inv2=9970209,inv6=3323403;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch>=1;
}
// cout<
Original: https://blog.csdn.net/m0_46222454/article/details/127812994
Author: Sunflower_ac
Title: 【题解】P2260 [清华集训2012]模积和（数学，整除分块）
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/656170/
转载文章受原作者版权保护。转载请注明原作者出处！