Eva

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 2471  Solved: 1551
Description

给定一个nxm的网格，请计算三点都在格点上的三角形共有多少个。下图为4x4的网格上的一个三角形。

注意三角形的三点不能共线。

输入一行，包含两个空格分隔的正整数m和n。

输出一个正整数，为所求三角形数量。

2 2

76


数据范围
1<=m,n<=1000

/**************************************************************

    Problem: 3505

    User: ictsing

    Language: C++

    Result: Accepted

    Time:344 ms

    Memory:1288 kb

****************************************************************/

 

#include<iostream>

#include<cstdio>

using namespace std;

typedef long long ll;

int gcd(int x,int y)

{

    if(y==0) return x;

    return gcd(y,x%y);

}

inline int read()

{

    int num=0,flag=1;

    char ch;

    do{

       ch=getchar();

       if(ch=='-') flag=-1;

    }while(ch<'0'||ch>'9');

    do{

    num=num*10+ch-'0';

        ch=getchar();

    }while(ch>='0'&&ch<='9');

    return num*flag;

}

int main()

{

    int n=read(),m=read();

    n++,m++;

    ll ans=1ll*m*n*(m*n-1)*(m*n-2)/6;

    for(int i=0;i<n;i++)

        for(int j=0;j<m;j++)

     if(i||j)

    {

        ll t=1ll*(gcd(i,j)-1)*(m-j)*(n-i);

        if(!i||!j) ans-=t;

        else ans-=2*t;

    }

    printf("%lld\n",ans);

    return 0;

}