BZOJ3505: [Cqoi2014]数三角形

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3505

Solution

排列组合加容斥。显然答案为C(n×m,3)-c(n,3)×m-c(m,3)×n-sum。sum表示三点一斜线的情况数。
枚举每条斜线所在的矩形，设长为x，宽为y，那这样的矩形有(n-x)×(m-y)个，可以用gcd求出这条斜线上的点数，然后乘以矩形数，因为斜线有两种方向所以再乘二，算出这种矩形不合法的方案数，减去即可。

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
ll n,m,ans;
ll gcd(ll x,ll y){
    for (ll t;y;t=x,y=t%(x=y));
    return x;
}
ll C(ll x){return x*(x-1)*(x-2)/6;}
int main(){
    scanf("%lld%lld",&n,&m); n++; m++;
    ans=C(n*m)-C(n)*m-C(m)*n;
    for (ll i=1;i<n;i++)
    for (ll j=1;j<m;j++)
        ans-=(gcd(i,j)-1)*(n-i)*(m-j)*2;
    printf("%lld",ans);
}