题解 P3166 【[CQOI2014]数三角形】

· · 题解

背景

小萌新 \varnothing 如何也想不到，此题存在 O(n) 的做法！！

思路

Part I

显然，总体思路应为：【三角形数量】等于【任选三个点的方案数】减去【三点共线的方案数】。

共有 (n+1)(m+1) 个点，故【任选三个点的方案数】为 C_{(n+1)(m+1)}^3。

【三点共线的方案数】等于【横着的】加【竖着的】加【斜着的】。

【横着的】指三点所在直线平行于 x 轴。共有 m+1 条横线，每条横线上有 n+1 个点，从这 n+1 个点中选取 3 个，方案数为 (m+1)\cdot C_{n+1}^3。

同理，【竖着的】指三点所在直线平行于 y 轴，方案数为 (n+1)\cdot C_{m+1}^3。

看来，我们现在最关心的是【斜着的】，斜着的直线按斜率正负分为两种，并且这两种的方案数是相等的。因此，我们只需要计算出斜率为正的方案数，再乘以 2 即可。

方便起见，不妨将核心计算内容——斜率为正的方案数记为 ans。

Part II

先考虑较朴素的 O(n^2) 做法。

在此之前，观察可以发现一个小小的结论：

假设网格中 AB 平行于底边 x 轴，长度为 i ，BC 平行于侧边 y 轴，长度为 j ，那么 AC 上的整点数量为 \gcd(i,j)+1。

那么我们可以枚举两点横坐标差 i，纵坐标差 j，则两点连线上的整点数量为 \gcd(i,j)+1（不算两端点自身的话有 \gcd(i,j)-1 个）。

对于每组横坐标差 i，纵坐标差 j 的点对，我们先选取两端点，再在他俩之间的 \gcd(i,j)-1 个点中任选一个作为第三个点，方案数为 \gcd(i,j)-1。

每组点对可以有 \gcd(i,j)-1 种方案，像这样横坐标差 i，纵坐标差 j 的点对共有 (n-i+1)(m-j+1) 个，故可以枚举 i,j 计算：

ans=\sum_{i=1}^n\sum_{j=1}^m(n-i+1)(m-j+1)(\gcd(i,j)-1)

直接计算这个式子复杂度 O(nm)=O(n^2)，考虑 \gcd 的计算的话甚至是 O(n^2\log n)。当然，对于本题的数据是绰绰有余了。

Part III

提供一个相当美妙并且相当好写的 O(n) 做法。

我们看到 [\gcd(i,j)=1] 这样的项时，总是按照莫比乌斯反演套路将其化为 \sum_{d\mid\gcd(i,j)}\mu(d)。

实际上，对于 \gcd(i,j) 这样的项时，也是有套路的，那就是根据欧拉反演将其化为 \sum_{d\mid\gcd(i,j)}\varphi(d)。

他的原理是欧拉函数的一个有趣性质：

n 的所有因子的欧拉函数和为 n ，即 \sum_{d\mid n}\varphi(d)=n。

证明及更详细的信息见 \varnothing 的博客。

也就是说：

ans=\sum_{i=1}^n\sum_{j=1}^{m}(n-i+1)(m-j+1)\left(\sum_{d\mid\gcd(i,j)}\varphi(d)-1\right)

考虑到 \varphi(1)=1，不妨先预先化简下，把 \varphi(1) 和 -1 抵消掉，免得以后麻烦：

ans=\sum_{i=1}^n\sum_{j=1}^{m}(n-i+1)(m-j+1)\sum_{d\mid\gcd(i,j)}^{d\ne 1}\varphi(d)

更复杂了？不妨先来看看 d|\gcd(i,j) 的含义：

i,j 的最大公约数的每个因子。

那不正是 i,j 的每个公约数吗？

枚举 i,j 再枚举他们的所有公约数，等价于枚举每个约数 d 再枚举 d 的 i 倍、j倍。

可以看出，d 的取值范围成了 [2,\min(n,m)]，i,j 最小可取 1，最大分别取 \left\lfloor\dfrac{n}{d}\right\rfloor,\left\lfloor\dfrac{m}{d}\right\rfloor，即：

ans=\sum_{d=2}^{\min(n,m)}\sum_{i=1}^{\lfloor{n/d}\rfloor}\sum_{j=1}^{\lfloor{m/d}\rfloor}(n-id+1)(m-jd+1)\varphi(d) =\sum_{d=2}^{\min(n,m)}\varphi(d)\sum_{i=1}^{\lfloor{n/d}\rfloor}(n-id+1)\sum_{j=1}^{\lfloor{m/d}\rfloor}(m-jd+1)

很明显，\sum_{i=1}^{\lfloor{n/d}\rfloor}(n-id+1) 是等差数列求和，

首项为 (n-d+1)，末项为 (n-\left\lfloor\dfrac{n}{d}\right\rfloor d+1) 即 (n\bmod d+1)，项数为 \left\lfloor\dfrac{n}{d}\right\rfloor，故：

\sum_{i=1}^{\lfloor{n/d}\rfloor}(n-id+1)=\dfrac{1}{2}(n-d+1+n\bmod d+1)\left\lfloor\dfrac{n}{d}\right\rfloor

同理有：

\sum_{j=1}^{\lfloor{m/d}\rfloor}(m-jd+1)=\dfrac{1}{2}(n-d+1+n\bmod d+1)\left\lfloor\dfrac{n}{d}\right\rfloor

最终得到：

ans=\dfrac{1}{4}\sum_{d=2}^{\min(n,m)}\varphi(d)(n-d+n\bmod d+2)\left\lfloor\dfrac{n}{d}\right\rfloor(m-d+m\bmod d+2)\left\lfloor\dfrac{m}{d}\right\rfloor

欧拉函数可以利用欧拉筛线性预处理出，枚举 d 复杂度 O(\min(n,m))=O(n)。

代码

#include <cstdio>
#include <iostream> 
using namespace std;
const int maxn = 1005;
int n, m, p[maxn], phi[maxn], tot;
bool mark[maxn];
long long ans;
long long C(long long x) { return x * (x-1) * (x-2) / 6; }
void sieve(int n) {
    phi[1] = 1;
    for(int i = 2; i <= n; ++i) {
        if(!mark[i]) p[++tot] = i, phi[i] = i - 1;
        for(int j = 1; j <= tot and p[j]*i <= n; ++j) {
            mark[p[j]*i] = true;
            if(i % p[j]) phi[p[j]*i] = phi[i] * (p[j]-1);
            else { phi[p[j]*i] = phi[i] * p[j]; break; }
        }
    }
}
int main() {
    scanf("%d %d", &n, &m);
    if(n > m) swap(n, m);
    sieve(n);
    for(int d = 2, x, y; d <= n; ++d)//记得 ans 要乘以 2，这里直接除以 2 就行了不用除以 4
        ans += (long long)phi[d]*(n-d+n%d+2)*(n/d)*(m-d+m%d+2)*(m/d)/2;
    ans = C((n+1)*(m+1)) - (m+1)*C(n+1) - (n+1)*C(m+1) - ans;
    printf("%lld\n", ans);
}

p.s

不考虑一些奇奇怪怪的 0ms 的话，\varnothing 当初交的时候是 29ms 最优解诶。

觉得蛮有意思的话也请点个赞吧，无论你是否看明白了。