自动搬运

查看原文

来自洛谷，原作者为

	maojun 猫君

搬运于2025-08-24 22:59:49，当前版本为作者最后更新于2024-06-22 16:49:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

看看怎么数数，推推式子。

首先同行同列的方案数是 $n{m\choose3}+m{n\choose3}$，这个是简单的。

不同行同列的话，斜率为负的线，贡献和斜率为正的线一样。这里统计斜率为正的线，最后答案 $\times2$ 即可。

考虑枚举最远的点对的横纵坐标差 $i,j$，满足这个条件的点对有 $(n-i)(m-j)$ 个。

做过 P1447 的话应该可以发现中间点有 $\gcd(i,j)-1$ 种方案。

于是有：

$$\mathrm{ans}=n{m\choose3}+m{n\choose3}+2(\sum\limits_{i=1}^n\sum\limits_{j=1}^m(n-i)(m-j)(\gcd(i,j)-1)) $$

---

其实后面就是套路了，建议自己推一推，反正不难。

看看怎么快速计算：

$$\begin{aligned} &\sum\limits_{i=1}^n\sum\limits_{j=1}^m(n-i)(m-j)(\gcd(i,j)-1)\\= &\sum\limits_{i=1}^n\sum\limits_{j=1}^m(n-i)(m-j)\gcd(i,j)-\sum\limits_{i=1}^n\sum\limits_{j=1}^m(n-i)(m-i) \end{aligned} $$

先看看后面的。

记 $\operatorname{sum}(n)=\sum\limits_{i=1}^ni=\dfrac{n(n+1)}2$，则：

$$\begin{aligned} &\sum\limits_{i=1}^n\sum\limits_{j=1}^m(n-i)(m-j)\\= &\sum\limits_{i=0}^{n-1}\sum\limits_{j=0}^{m-1}ij\\= &\operatorname{sum}(n-1)\operatorname{sum}(m-1) \end{aligned} $$

再看看前面的，不妨设 $n\le m$。则：

$$\begin{aligned} &\sum\limits_{i=1}^n\sum\limits_{j=1}^m(n-i)(m-j)\gcd(i,j)\\= &\sum\limits_{i=1}^n\sum\limits_{j=1}^m(n-i)(m-j)\sum\limits_{d\mid i,d\mid j}\varphi(d)\\= &\sum\limits_{d=1}^n\varphi(d)\sum\limits_{i=1}^{\left\lfloor\frac nd\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac md\right\rfloor}(n-id)(m-jd) \end{aligned} $$

记 $f(n,d)=\sum\limits_{i=1}^{\left\lfloor\frac nd\right\rfloor}(n-id)=n\left\lfloor\frac nd\right\rfloor-d\operatorname{sum}(\left\lfloor\frac nd\right\rfloor)$。

则上式可继续简化：

$$\begin{aligned} =&\sum\limits_{d=1}^n\varphi(d)\sum\limits_{i=1}^{\left\lfloor\frac nd\right\rfloor}(n-id)\sum\limits_{j=1}^{\left\lfloor\frac md\right\rfloor}(m-jd)\\ =&\sum\limits_{d=1}^n\varphi(d)f(n,d)f(m,d) \end{aligned} $$

即可做到 $O(n)$。

typedef long long ll;
const int N=5e4+5,MOD=1e9+7;
int n,m,phi[N];
int pc=0,p[N];bool vis[N];
inline void seive(){
	phi[1]=1;
	for(int i=2;i<=n;i++){
		if(!vis[i]){p[++pc]=i;phi[i]=i-1;}
		for(int j=1,k;j<=pc&&(k=i*p[j])<=n;j++){
			vis[k]=true;
			if(i%p[j]==0){phi[k]=phi[i]*p[j];break;}
			phi[k]=phi[i]*(p[j]-1);
		}
	}
}

inline ll C3(ll x){return x*(x-1)*(x-2)/6%MOD;}
inline ll sum(ll x){return x*(x+1)/2%MOD;}
inline ll f(ll n,int d){return(n/d*n-d*sum(n/d))%MOD;}
int main(){
	scanf("%d%d",&n,&m);if(n>m)swap(n,m);
	seive();
	ll res=0;
	for(int i=1;i<=n;i++)res=(res+phi[i]*f(n,i)%MOD*f(m,i))%MOD;
	res=(res-sum(n-1)*sum(m-1))*2+n*C3(m)+m*C3(n);
	printf("%lld\n",(res%MOD+MOD)%MOD);
	return 0;
}

---

复杂度更优的做法：

$$\begin{aligned} \mathrm{ans}&=\sum\limits_{d=1}^n\varphi(d)f(n,d)f(m,d)\\ &=\sum\limits_{d=1}^n\varphi(d)(n\left\lfloor\frac nd\right\rfloor-d\operatorname{sum}(\left\lfloor\frac nd\right\rfloor))(m\left\lfloor\frac md\right\rfloor-d\operatorname{sum}(\left\lfloor\frac md\right\rfloor))\\ &=\sum\limits_{d=1}^nn\left\lfloor\frac nd\right\rfloor m\left\lfloor\frac md\right\rfloor\varphi(d)\\ &-\sum\limits_{d=1}^n(n\left\lfloor\frac nd\right\rfloor\operatorname{sum}(\left\lfloor\frac md\right\rfloor)+m\left\lfloor\frac md\right\rfloor\operatorname{sum}(\left\lfloor\frac nd\right\rfloor))d\varphi(d)\\ &+\sum\limits_{d=1}^n\operatorname{sum}(\left\lfloor\frac nd\right\rfloor)\operatorname{sum}(\left\lfloor\frac md\right\rfloor)d^2\varphi(d)\\ \end{aligned} $$

考虑整除分块，只需快速求 $\sum\limits_{i=1}^n\varphi(i),\sum\limits_{i=1}^ni\varphi(i),\sum\limits_{i=1}^ni^2\varphi(i)$。

做法一：线性筛预处理+整除分块，复杂度 $O(n+T\sqrt n)$。

记 $f_k(x)=x^k\varphi(x)$，具体地：

• $f_k(p)=p^k(p-1)$

• 对于 $\gcd(x,y)=1$，$f_k(xy)=f_k(x)f_k(y)$

• 对于 $p\mid x$，$f_k(xp)=f_k(x)p^{k+1}$

这样就可以线性筛出来。

做法二：杜教筛+整除分块，复杂度 $O(n^{\frac23})$。

因为有 $\left\lfloor\dfrac{\left\lfloor\dfrac na\right\rfloor}b\right\rfloor=\left\lfloor\dfrac n{ab}\right\rfloor$，所以复杂度是对的。

具体地，构造 $g_k(x)=x^k$，则有

$$\begin{aligned} (f_k*g_k)(n)&=\sum\limits_{d\mid n}f_k(d)g_k(\dfrac nd)\\ &=\sum\limits_{d\mid n}d^k\varphi(d)(\dfrac nd)^k\\ &=n^k\sum\limits_{d\mid n}\varphi(d)\\ &=n^{k+1} \end{aligned} $$

$g_k$ 和 $f_k*g_k$ 都可以快速求前缀和，这样就可以杜教筛了。