team2012-E1-mysol-0005

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
/* 解题报告 //

给出一个 n * m 的网格，要求选择三个格点构成三角形，问总方案数

直接计算三角形个数显然太麻烦，于是考虑用网格上选三点的方案数
减去网格上选三点且三点共线的方案数，得到要求的答案

为了求出共线三点的方案数，可以先求出在一个 i * j 的网格中
以 (i, j) 为三点中最靠下的点，有多少种共线三点的方案数，记为 a[i][j]
则 a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + something
等式右边的前面三项是把比 i * j 小的网格的方案数加到 a[i][j] 中
于是现在只要考虑以 (0, 0) 为左上角，(i, j) 为右下角，三点共线的方案数
这个值即为 gcd(i, j) - 1，也就是 something 的值

有了 a[i][j] 后就好算了，先用 C(n * m, 3) 得到网格上选三点的方案数
再枚举共线三点中最靠下的点 i, j，方案数减去 a[i][j] 和 a[i][m - j]
另外也要考虑到在同一竖直和同一水平方向的三点共线数量
即在方案数中，还要减去 i * (i - 1) / 2 和 j * (j - 1) / 2

long long 的精度超过 (1000 ^ 2) ^ 3，足够存下答案，所以不需要大整数

// By 猛犸也钻地 @ 2012.07.19 */
}}}

{{{
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long LL;

LL a[1001][1001];

int main(){
    for(int i=1;i<=1000;i++) for(int j=1;j<=1000;j++)
        a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+__gcd(i,j)-1;
    int n,m;
    while(scanf("%d%d",&n,&m)==2){
        LL ans=(n*m+n+m+1)*LL(n*m+n+m)*(n*m+n+m-1)/6;
        for(int i=0;i<=n;i++) for(int j=0;j<=m;j++){
            ans-=a[i][j]+a[i][m-j];
            ans-=i*(i-1)/2+j*(j-1)/2;
        }
        printf("%lld\n",ans);
    }
}
}}}

/* 解题报告 //
给出一个 n * m 的网格，要求选择三个格点构成三角形，问总方案数
直接计算三角形个数显然太麻烦，于是考虑用网格上选三点的方案数
减去网格上选三点且三点共线的方案数，得到要求的答案
为了求出共线三点的方案数，可以先求出在一个 i * j 的网格中
以 (i, j) 为三点中最靠下的点，有多少种共线三点的方案数，记为 a[i][j]
则 a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + something
等式右边的前面三项是把比 i * j 小的网格的方案数加到 a[i][j] 中
于是现在只要考虑以 (0, 0) 为左上角，(i, j) 为右下角，三点共线的方案数
这个值即为 gcd(i, j) - 1，也就是 something 的值
有了 a[i][j] 后就好算了，先用 C(n * m, 3) 得到网格上选三点的方案数
再枚举共线三点中最靠下的点 i, j，方案数减去 a[i][j] 和 a[i][m - j]
另外也要考虑到在同一竖直和同一水平方向的三点共线数量
即在方案数中，还要减去 i * (i - 1) / 2 和 j * (j - 1) / 2
long long 的精度超过 (1000 ^ 2) ^ 3，足够存下答案，所以不需要大整数
// By 猛犸也钻地 @ 2012.07.19 */

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
LL a[1001][1001];
int main(){
    for(int i=1;i<=1000;i++) for(int j=1;j<=1000;j++)
        a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+__gcd(i,j)-1;
    int n,m;
    while(scanf("%d%d",&n,&m)==2){
        LL ans=(n*m+n+m+1)*LL(n*m+n+m)*(n*m+n+m-1)/6;
        for(int i=0;i<=n;i++) for(int j=0;j<=m;j++){
            ans-=a[i][j]+a[i][m-j];
            ans-=i*(i-1)/2+j*(j-1)/2;
        }
        printf("%lld\n",ans);
    }
}