prow2012-A3-0005

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

此题求：一个n×m的格点矩形中，三角形数量。 

可得最后答案是C((N+1)*(M+1),3)-共线的三角形个数

枚举这些共线三角形的两个顶点，另一个顶点是在网格上的数量是gcd(x,y)-1，注意需要*2，因为矩形有两条对角线。

{{{

#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <set>
#include <map>
#include <sstream>
#include <string>
#include <math.h>
using namespace std;
typedef long long LL;
int gcd(int a,int b){
    return b==0?a:gcd(b,a%b);
}
int main(){
    int N,M,x,y,num;
    while(scanf("%d%d",&N,&M)!=EOF){
        LL tot = (N+1)*(M+1);
        tot = (tot*(tot-1)*(tot-2))/6;
        for (x = 0;x<=N;x++)
            for (y=0;y<=M;y++){
                if (x==0||y==0)
                     num = max(x,y)-1;
                else 
                     num = gcd(x,y)-1,num*=2;
            //printf("%d %d :%d\n",x,y,num);
                if (num>0)
                    tot-=1LL*num*((N-x+1)*(M-y+1));
            }
        cout<<tot<<endl;
    }
}

}}}

此题求：一个n×m的格点矩形中，三角形数量。

可得最后答案是C((N+1)*(M+1),3)-共线的三角形个数

枚举这些共线三角形的两个顶点，另一个顶点是在网格上的数量是gcd(x,y)-1，注意需要*2，因为矩形有两条对角线。

#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <set>
#include <map>
#include <sstream>
#include <string>
#include <math.h>
using namespace std;
typedef long long LL;
int gcd(int a,int b){
    return b==0?a:gcd(b,a%b);
}
int main(){
    int N,M,x,y,num;
    while(scanf("%d%d",&N,&M)!=EOF){
        LL tot = (N+1)*(M+1);
        tot = (tot*(tot-1)*(tot-2))/6;
        for (x = 0;x<=N;x++)
            for (y=0;y<=M;y++){
                if (x==0||y==0)
                     num = max(x,y)-1;
                else 
                     num = gcd(x,y)-1,num*=2;
            //printf("%d %d :%d\n",x,y,num);
                if (num>0)
                    tot-=1LL*num*((N-x+1)*(M-y+1));
            }
        cout<<tot<<endl;
    }
}