题解：P10636 BZOJ3518 点组计数

· · 题解

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

首先同行同列的方案数是 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)，具体地：

这样就可以线性筛出来。

做法二：杜教筛+整除分块，复杂度 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}