team2012-F3-sol-0005

从 Trac 迁移的文章

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

原文章内容如下：

{{{
题意：计算(n+1)*(m+1)的格板上的所有三角形数目
解法：选取三角形三个顶点有C((n+1)*(m+1), 3)种，再减去三点共线的情况。
三点共线的情况有：
此线斜率大于零、斜率小于零、斜率为零、斜率为无穷
后两种由(m+1)*C(n+1,3)和(n+1)*C(m+1,3)得到；由对称性，前两种个数相同，且每条线段可以视为从(0,0)到(i,j)的线段平移得到，枚举(i,j)即可，中间连线上的点为gcd(i,j)-1
}}}
{{{
#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;

typedef long long LL;

int n, m;

LL gcd(LL a, LL b)
{
    while(b)
    {
        LL c = a % b;
        a = b;
        b = c;
    }
    return a;
}

LL gao()
{
    LL ret = 0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            LL g = gcd(i, j);
            if(--g)
                ret += g*(n-i+1)*(m-j+1);
        }
    return ret;
}

LL c3(LL a)
{
    return a*(a-1)/2*(a-2)/3;
}

int main()
{
    while(cin>>n>>m)
    {
        LL ans = c3((n+1)*(m+1));
        ans -= (n+1) * c3(m+1);
        ans -= (m+1) * c3(n+1);
        ans -= 2 * gao();
        cout<<ans<<endl;
    }

    return 0;
}
}}}

题意：计算(n+1)*(m+1)的格板上的所有三角形数目
解法：选取三角形三个顶点有C((n+1)*(m+1), 3)种，再减去三点共线的情况。
三点共线的情况有：
此线斜率大于零、斜率小于零、斜率为零、斜率为无穷
后两种由(m+1)*C(n+1,3)和(n+1)*C(m+1,3)得到；由对称性，前两种个数相同，且每条线段可以视为从(0,0)到(i,j)的线段平移得到，枚举(i,j)即可，中间连线上的点为gcd(i,j)-1

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long LL;
int n, m;
LL gcd(LL a, LL b)
{
    while(b)
    {
        LL c = a % b;
        a = b;
        b = c;
    }
    return a;
}
LL gao()
{
    LL ret = 0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            LL g = gcd(i, j);
            if(--g)
                ret += g*(n-i+1)*(m-j+1);
        }
    return ret;
}
LL c3(LL a)
{
    return a*(a-1)/2*(a-2)/3;
}
int main()
{
    while(cin>>n>>m)
    {
        LL ans = c3((n+1)*(m+1));
        ans -= (n+1) * c3(m+1);
        ans -= (m+1) * c3(n+1);
        ans -= 2 * gao();
        cout<<ans<<endl;
    }
    return 0;
}