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
",ans);
51     }
52     return 0;
53 }

View Code