首页 > 代码库 > [BZOJ][CQOI2014]数三角形

[BZOJ][CQOI2014]数三角形

Description

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

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

Input

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

Output

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

Sample Input

2 2

Sample Output

76

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

      因为就在做这道题之前看的一道题……下意识以为只有直线和对角线的情况,然后搞成O(n)算法似乎自己比其他写题解的神犇厉害??事实上我错了,,,orz(雾(跪地(无奈(orz(%%%(逃

      首先,显然的,不考虑三点共线共有C(n*m,3)种方法,所以问题转化为三点共线有几种情况?

      在(x1,y1) (x2,y2)两点构成的线段(不含端点)上有gcd(x1-x2,y1-y2)-1个整点。

      所以我们可以在logn的时间求出一条线段中的整点个数,但枚举两个点显然要超时,所以我们只枚举一个点的坐标,它与(0,0)显然构成了唯一的一条线段,然后我们发现这条线段其实可以移动,所以就将一条线段的解*(n-x)*(m-y)

      相减就得到答案啦~~

#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
ll n,m;
ll gcd(ll a,ll b){
    return b?gcd(b,a%b):a;
}
int main(){
    scanf("%lld%lld",&n,&m);
    n++;m++;
    ll ans=(n*m)*(n*m-1)*(n*m-2)/6;    
    for(int i=0;i<n;i++)
    for(int j=0;j<m;j++){
        ll c;
        if(!i)c=j-1;
        if(!j)c=i-1;
        if(i&&j)c=gcd(i,j)-1;
        if(c<0)c=0;
        if(i&&j)ans-=c*(n-i)*(m-j)*2;else ans-=c*(n-i)*(m-j);
    }
    printf("%lld",ans);
}

 

[BZOJ][CQOI2014]数三角形