bzoj 3505 [Cqoi2014]数三角形（组合计数）

【题目链接】

　　http://www.lydsy.com/JudgeOnline/problem.php?id=3505

【题意】

　　在n个格子中任选3点构成三角形的方案数。

【思路】

　　任选3点-3点共线的情况。

【代码】

 1 #include<cstdio>
 2 #include<iostream>
 3 using namespace std;
 4 
 5 typedef long long ll;
 6 
 7 ll C[1000003][5]; 
 8 
 9 void get_pre(int n)
10 {
11     C[0][0]=1;
12     for(int i=1;i<=n;i++) {
13         C[i][0]=1;
14         for(int j=1;j<=3;j++)
15             C[i][j]=C[i-1][j]+C[i-1][j-1];
16     }
17 }
18 int gcd(int i,int j)
19 {
20     return j==0?i:gcd(j,i%j);
21 }
22 int n,m;
23 
24 int main()
25 {
26     scanf("%d%d",&n,&m);
27     n++,m++;
28     if(n>m) swap(n,m);
29     get_pre(n*m);
30     ll ans=C[n*m][3],tmp=0;
31     ans-=n*C[m][3]+m*C[n][3];
32     for(int i=1;i<n;i++) for(int j=1;j<m;j++) {
33         int x=gcd(i,j)+1;
34         if(x>2)
35             ans-=(x-2)*2*(n-i)*(m-j);
36     }
37     printf("%lld
",ans);
38     return 0;
39 }