[CQOI2014]数三角形 组合数 + 容斥 + gcd

推导过程 ： 组合数+容斥原理+gcd

正确做法是暴力的一种优化，ans=所有情况 - 平行坐标轴的三点共线 - 斜线三点共线

如果快速求斜线三点共线：

首先要知道一个结论，对于点(a,b) (x,y)连成的线段而言(其中a>x,b>y)，

在它们中间有gcd(a-x,b-x)-1个整点，因此基本的思路就是枚举两个点，

然后第3个点就是gcd(a-x,b-x)-1种可能了

至于为什么第3个点一定要在中间，是为了保证不重不漏，只用两边的点统计中间的点，

然而这样复杂度太高，于是可以发现，可以将这两个点组成的线段中左下那个端点平移至原点，

这样相当于只要枚举一个点，并且由于要考虑k<0的情况，因为矩形是有对称性的，

所以要求原点+一个点 与 (0,m)+一个点 的和就可以直接2 *（原点+一个点）

由于长的一样的线有很多，于是问题就转化为如果求这些一样的线的个数，

那么可以发现，这样任意一条线，向上只能平移(n - i)，向下(m - j)次，

所以可能性就为(n - i + 1) * (m - j + 1),其中+1是因为可以向上移动0个单位

但由于这里n,m一开始就加了1，所以这个式子就不用+1了

因此枚举每个点即可

#include
using namespace std;
#define R register int
#define LL long long
LL n,m,ans,go;

int gcd(int x,int y)
{
    if(!y) return x;
    else return gcd(y,x%y);
}

void work()
{
    scanf("%lld%lld",&n,&m);
    ++n,++m;//因为是一个网格，所以真正的坐标系其实有(n+1,m+1)
    go=n*m;
    ans=go * (go - 1) * (go - 2) / 6 - n * m * (m - 1) * (m - 2) / 6 - m * n * (n - 1) * (n - 2) / 6;//记得除掉取出数列的全排列
    for(R i=1; i//因为是取了原点，所以相当于坐标系是从0开始了
        for(R j=1; j//枚举这个点
            ans-=(LL)2 * (LL)(gcd(i,j) - 1) * (LL)(n - i) * (LL)(m - j); 
    printf("%lld
",ans);
}

int main()
{
    freopen("in.in","r",stdin);
    work();
    fclose(stdin);
    return 0;
}