UVALive 3295

题目大意：见刘汝佳《算法竞赛入门经典——训练指南》P173

解题思路：

　　每一个合法的三角形的三个顶点都不在同一直线上，那么问题其实就是在求所有不全在同一直线上的三点的组合数。

　　我们可以利用容斥原理，先求出所有的三个顶点的组合数C[(n+1)*(m+1)][3]。全在同一直线上的三个网格顶点有三种：三点在同一水平线上的，三点在同一竖直线上的，三点在同一斜线上的。前两种不难求，因此不再赘述，这里重点讲解第三种。

　　设三点坐标为（x1,y1），（x2,y2），（x3,y3），且x1 < x2 < x3，y1 < y2 < y3，设 x2-x1 = i，x3-x2 = j，当且仅当 i*（y3-y2） = j*（y2-y1）时，三点在同一斜线上。那么我们可以枚举 i 和 j ，求出 g = gcd（i,j），对于每一个（i,j），再从 1 开始枚举 k ，则此时 y3-y2 = k*j/g，y2-y1 = k*i/g（当 y3 - y1 >= m+1时退出循环），这样就可以知道 x3-x1 和 y3-y1 的值了，接下来就只需要求出放得下多少条这样的斜线就可以。

AC代码：

 #include <iostream>

 #include <cstdio>

 #include <algorithm>

 using namespace std;

 typedef long long ll;

 const int maxn=+;

 ll C[maxn][];

 void init(){

     C[][]=;

     C[][]=C[][]=;

     for(int n=;n<maxn;n++){

         C[n][]=;

         if(n<=)    C[n][n]=;

         for(int m=;m<min(,n);m++){

             C[n][m]=C[n-][m-]+C[n-][m];

         }

     }

 }

 int gcd(int a,int b){

     if(b==)    return a;

     return gcd(b,a%b);

 }

 int main(){

     init();

     int n,m;

     int kase=;

     while(scanf("%d%d",&n,&m)==&&n&&m){

         n++,m++;

         if(n>m) swap(n,m);

         ll ans=C[n*m][];

         ans-=C[n][]*m;

         ans-=C[m][]*n;

         ll t=;

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

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

                 int gd=gcd(i,j);

                 for(int k=;;k++){

                     int id=k*j/gd,ij=k*i/gd;

                     if(id+ij>=m)  break;

                     t+=(n-(i+j))*(m-(k*(i+j)/gd));

                 }

             }

         }

         ans-=t*;

         printf("Case %d: %lld\n",kase++,ans);

     }

     return ;

 }

巴特西

UVALive 3295

最新文章

热门文章