【题解】P2260 [清华集训2012]模积和（数学，整除分块）

【题解】P2260 [清华集训2012]模积和

比较简单的一道推式子的题。(清华集训居然会出这种水题的吗)

题目链接

P2260 [清华集训2012]模积和

题意概述

求

∑i=1n∑j=1m(nmodi)×(mmodj),i≠j" role="presentation" style="text-align: center; position: relative;">∑i=1n∑j=1m(nmodi)×(mmodj),i≠j$$\sum _{i=1}^n\sum _{j=1}^m(nmodi)\times (mmodj),i\ne j$$

mod19940417" role="presentation" style="position: relative;">mod19940417$\mathrm{mod}19940417$ 的值

思路分析

直接容斥一下然后推式子即可，见下：

∑i=1n∑j=1m(nmodi)(mmodj)=∑i=1n(nmodi)∑j=1m(mmodj)−∑i=1min(n,m)(nmodi)(mmodj)=∑i=1n(nmodi)∑j=1m(m−⌊mj⌋×j)−∑i=1min(n,m)(n−⌊ni⌋×i)(m−⌊mi⌋×i)=∑i=1n(nmodi)(∑j=1mm−∑j=1m⌊mj⌋×j)−∑i=1min(n,m)(nm−n⌊mi⌋×i−m⌊ni⌋×i+⌊mi⌋⌊ni⌋×i2)=∑i=1n(nmodi)(m2−∑j=1m⌊mj⌋×j)−∑i=1min(n,m)nm+n∑i=1min(n,m)⌊mi⌋×i+m∑i=1min(n,m)⌊ni⌋×i−∑i=1min(n,m)⌊ni⌋⌊mi⌋×i2=(m2−∑j=1m⌊mj⌋×j)∑i=1n(nmodi)−min(n,m)nm+n∑i=1min(n,m)⌊mi⌋×i+m∑i=1min(n,m)⌊ni⌋×i−∑i=1min(n,m)⌊ni⌋⌊mi⌋×i2=(m2−∑j=1m⌊mj⌋×j)(n2−∑i=1n⌊ni⌋×i)−min(n,m)nm+n∑i=1min(n,m)⌊mi⌋×i+m∑i=1min(n,m)⌊ni⌋×i−∑i=1min(n,m)⌊ni⌋⌊mi⌋×i2" role="presentation" style="position: relative;">∑i=1n∑j=1m(nmodi)(mmodj)=∑i=1n(nmodi)∑j=1m(mmodj)−∑i=1min(n,m)(nmodi)(mmodj)=∑i=1n(nmodi)∑j=1m(m−⌊mj⌋×j)−∑i=1min(n,m)(n−⌊ni⌋×i)(m−⌊mi⌋×i)=∑i=1n(nmodi)(∑j=1mm−∑j=1m⌊mj⌋×j)−∑i=1min(n,m)(nm−n⌊mi⌋×i−m⌊ni⌋×i+⌊mi⌋⌊ni⌋×i2)=∑i=1n(nmodi)(m2−∑j=1m⌊mj⌋×j)−∑i=1min(n,m)nm+n∑i=1min(n,m)⌊mi⌋×i+m∑i=1min(n,m)⌊ni⌋×i−∑i=1min(n,m)⌊ni⌋⌊mi⌋×i2=(m2−∑j=1m⌊mj⌋×j)∑i=1n(nmodi)−min(n,m)nm+n∑i=1min(n,m)⌊mi⌋×i+m∑i=1min(n,m)⌊ni⌋×i−∑i=1min(n,m)⌊ni⌋⌊mi⌋×i2=(m2−∑j=1m⌊mj⌋×j)(n2−∑i=1n⌊ni⌋×i)−min(n,m)nm+n∑i=1min(n,m)⌊mi⌋×i+m∑i=1min(n,m)⌊ni⌋×i−∑i=1min(n,m)⌊ni⌋⌊mi⌋×i2$$\begin{array}{rl}\sum _{i=1}^n\sum _{j=1}^m(nmodi)(mmodj)& =\sum _{i=1}^n(nmodi)\sum _{j=1}^m(mmodj)-\sum _{i=1}^{min(n,m)}(nmodi)(mmodj)\\ & =\sum _{i=1}^n(nmodi)\sum _{j=1}^m(m-\lfloor {\displaystyle \frac{m}{j}}\rfloor \times j)-\sum _{i=1}^{min(n,m)}(n-\lfloor {\displaystyle \frac{n}{i}}\rfloor \times i)(m-\lfloor {\displaystyle \frac{m}{i}}\rfloor \times i)\\ & =\sum _{i=1}^n(nmodi)(\sum _{j=1}^{m}m-\sum _{j=1}^m\lfloor {\displaystyle \frac{m}{j}}\rfloor \times j)-\sum _{i=1}^{min(n,m)}(nm-n\lfloor {\displaystyle \frac{m}{i}}\rfloor \times i-m\lfloor {\displaystyle \frac{n}{i}}\rfloor \times i+\lfloor {\displaystyle \frac{m}{i}}\rfloor \lfloor {\displaystyle \frac{n}{i}}\rfloor \times i^2)\\ & =\sum _{i=1}^n(nmodi)(m^2-\sum _{j=1}^m\lfloor {\displaystyle \frac{m}{j}}\rfloor \times j)-\sum _{i=1}^{min(n,m)}nm+n\sum _{i=1}^{min(n,m)}\lfloor {\displaystyle \frac{m}{i}}\rfloor \times i+m\sum _{i=1}^{min(n,m)}\lfloor {\displaystyle \frac{n}{i}}\rfloor \times i-\sum _{i=1}^{min(n,m)}\lfloor {\displaystyle \frac{n}{i}}\rfloor \lfloor {\displaystyle \frac{m}{i}}\rfloor \times i^2\\ & =(m^2-\sum _{j=1}^m\lfloor {\displaystyle \frac{m}{j}}\rfloor \times j)\sum _{i=1}^n(nmodi)-min(n,m)nm+n\sum _{i=1}^{min(n,m)}\lfloor {\displaystyle \frac{m}{i}}\rfloor \times i+m\sum _{i=1}^{min(n,m)}\lfloor {\displaystyle \frac{n}{i}}\rfloor \times i-\sum _{i=1}^{min(n,m)}\lfloor {\displaystyle \frac{n}{i}}\rfloor \lfloor {\displaystyle \frac{m}{i}}\rfloor \times i^2\\ & =(m^2-\sum _{j=1}^m\lfloor {\displaystyle \frac{m}{j}}\rfloor \times j)(n^2-\sum _{i=1}^n\lfloor {\displaystyle \frac{n}{i}}\rfloor \times i)-min(n,m)nm+n\sum _{i=1}^{min(n,m)}\lfloor {\displaystyle \frac{m}{i}}\rfloor \times i+m\sum _{i=1}^{min(n,m)}\lfloor {\displaystyle \frac{n}{i}}\rfloor \times i-\sum _{i=1}^{min(n,m)}\lfloor {\displaystyle \frac{n}{i}}\rfloor \lfloor {\displaystyle \frac{m}{i}}\rfloor \times i^2\end{array}$$

发现前四项都可以整除分块随便求。

我们考虑最后一项怎么求。

首先考虑 ∑i=1min(n,m)⌊ni⌋⌊mi⌋" role="presentation" style="position: relative;">∑i=1min(n,m)⌊ni⌋⌊mi⌋$\sum _{i=1}^{min(n,m)}\lfloor {\displaystyle \frac{n}{i}}\rfloor \lfloor {\displaystyle \frac{m}{i}}\rfloor$，这实际上也可以整除分块，只不过需要二维整除分块。

其实它和一般的整除分块区别也不大，很显然，每次只需要改一下块长就好了。

具体地，每次求 r" role="presentation" style="position: relative;">r$r$ 时：

r=min(⌊n⌊nl⌋⌋,⌊m⌊ml⌋⌋)" role="presentation" style="text-align: center; position: relative;">r=min(⎢⎣⎢⎢⎢⎢n⌊nl⌋⎥⎦⎥⎥⎥⎥,⎢⎣⎢⎢⎢⎢m⌊ml⌋⎥⎦⎥⎥⎥⎥)$$r=min(\lfloor {\displaystyle \frac{n}{\lfloor {\displaystyle \frac{n}{l}}\rfloor }}\rfloor ,\lfloor {\displaystyle \frac{m}{\lfloor {\displaystyle \frac{m}{l}}\rfloor }}\rfloor )$$

时间复杂度是 O(min(n,m))" role="presentation" style="position: relative;">O(min−−−√(n,m))$O(\sqrt{min}(n,m))$。

然后考虑 ∑i=1min(n,m)i2" role="presentation" style="position: relative;">∑i=1min(n,m)i2$\sum _{i=1}^{min(n,m)}{i}^2$ 怎么求。

有一个结论：

12+22+32+⋯+n2=n(n+1)(2n+1)6" role="presentation" style="text-align: center; position: relative;">12+22+32+⋯+n2=n(n+1)(2n+1)6$$1^2+2^2+3^2+\cdots +n^2={\displaystyle \frac{n(n+1)(2n+1)}{6}}$$

所以我们就可以求出整个的式子了。

易错点

19940417" role="presentation" style="position: relative;">19940417$19940417$ 不是素数，所以请注意：

模意义下计算 x" role="presentation" style="position: relative;">x$x$ 的逆元只有当 mod" role="presentation" style="position: relative;">mod$mod$ 为素数时才能使用 qpow(x,mod−2)" role="presentation" style="position: relative;">qpow(x,mod−2)$qpow(x,mod-2)$！！！

模意义下计算 x" role="presentation" style="position: relative;">x$x$ 的逆元只有当 mod" role="presentation" style="position: relative;">mod$mod$ 为素数时才能使用 qpow(x,mod−2)" role="presentation" style="position: relative;">qpow(x,mod−2)$qpow(x,mod-2)$！！！

模意义下计算 x" role="presentation" style="position: relative;">x$x$ 的逆元只有当 mod" role="presentation" style="position: relative;">mod$mod$ 为素数时才能使用 qpow(x,mod−2)" role="presentation" style="position: relative;">qpow(x,mod−2)$qpow(x,mod-2)$！！！

我是不会告诉你我在这挂了一个小时的……

所以可以使用 exgcd 预处理出来 2" role="presentation" style="position: relative;">2$2$ 和 6" role="presentation" style="position: relative;">6$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<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
 
int qpow(int a,int T)
{
	int ret=1;
	while(T)
	{
		if(T&1)(ret*=a)%=mod;
		(a*=a)%=mod;T>>=1;
	}
//	cout<
	return ret;
}
 
int work(int n,int k)
{
	int ret=0;
	for(int l=1,r;l<=n;l=r+1)
	{
		if(k/l==0)break;
		r=min(k/(k/l),n);
		(ret+=(k/l)*(l+r)%mod*(r-l+1)%mod*inv2)%=mod;
	}
	return ret;
}
 
int get(int n)
{
	return n*(n+1)%mod*(2*n+1)%mod*inv6%mod;
}
 
int work2(int n,int k,int p)
{
	int ret=0;
	for(int l=1,r;l<=n;l=r+1)
	{
		r=min({k/(k/l),p/(p/l),n});
		(ret+=(k/l)*(p/l)%mod*(get(r)-get(l-1)+mod)%mod)%=mod;
	}
	return ret;
}
 
signed main()
{
	int n,m;
	n=read();m=read();
	int sumn=work(n,n),summ=work(m,m);
	int sumM=work(min(n,m),m),sumN=work(min(n,m),n);
	int ans1=(n*n%mod-sumn+mod)%mod*(m*m%mod-summ+mod)%mod;
	int ans2=(min(n,m)*n%mod*m%mod+mod)%mod;
	int ans3=n*sumM%mod;
	int ans4=m*sumN%mod;
	int ans5=work2(min(n,m),n,m);
	cout<<((((ans1-ans2+mod)%mod+ans3)%mod+ans4)%mod-ans5+mod)%mod<<"\n";
	return 0;
}