BZOJ 3505: [Cqoi2014]数三角形 [组合计数]

3505: [Cqoi2014]数三角形

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

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

1<=m,n<=1000

$n++ m++$

$ans={nm\choose 3}-n*{m\choose 3}-m*{n\choose 3}-斜线上的情况$

n和m很小，我们直接枚举以(0,0)为左端点的斜线，以两端点为两个点，中间的第三个点有$(x,y)-1$种选择，然后乘上平移的方案数再乘以2，斜线还有反向

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

typedef long long ll;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

ll n,m,ans;

int gcd(int a,int b){return b==?a:gcd(b,a%b);}

int main(){

    n=read()+;m=read()+;

    ll x=n*m;

    ans+=x*(x-)*(x-)/;

    ans-=m*n*(n-)*(n-)/+n*m*(m-)*(m-)/;

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

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

            ans-=(n-i)*(m-j)*(gcd(i,j)-)<<;

    printf("%lld",ans);

}

巴特西

BZOJ 3505: [Cqoi2014]数三角形 [组合计数]

3505: [Cqoi2014]数三角形

最新文章

热门文章