首页 > 代码库 > zoj 3647 Gao the Grid

zoj 3647 Gao the Grid

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4837

先求出从所有点随机找出三个点的组合数,然后去掉共线的,平行好去掉,斜线就需要枚举矩形,也就是枚举两个端点形成向量。

 1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define maxn 1000 5 #define ll long long 6 using namespace std; 7  8 ll c[maxn][maxn]; 9 int n,m;10 ll gcd(ll a,ll b)11 {12     if(b==0) return a;13     else return gcd(b,a%b);14 }15 16 ll cnr(int n,int r)17 {18     if(n<r)return 0;19     if(n-r<r)r=n-r;20     int i,j;21     ll ret=1;22     for(i=0,j=1;i<r;i++)23     {24         ret*=(n-i);25         for(;j<=r&&ret%j==0;j++)ret/=j;26     }27     return ret;28 }29 30 31 int main()32 {33     while(scanf("%d%d",&n,&m)!=EOF)34     {35         ll ans=cnr((n+1)*(m+1),3);36         if(n+1>=3)37         ans-=(m+1)*cnr(n+1,3);38         if(m+1>=3)39         ans-=(n+1)*cnr(m+1,3);40         for(int i=2; i<=n; i++)41         {42             for(int j=2; j<=m; j++)43             {44                 if(gcd(i,j)-1)45                 {46                     ans-=(gcd(i,j)-1)*(n-i+1)*(m-j+1)*2;47                 }48             }49         }50         printf("%lld\n",ans);51     }52     return 0;53 }
View Code

 

zoj 3647 Gao the Grid