组合数学+gcd BZOJ3505 [Cqoi2014]数三角形

3505: [Cqoi2014]数三角形

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 1543 Solved: 945
[Submit][Status][Discuss]

Description

给定一个nxm的网格，请计算三点都在格点上的三角形共有多少个。下图为4x4的网格上的一个三角形。

注意三角形的三点不能共线。

Input

输入一行，包含两个空格分隔的正整数m和n。

Output

输出一个正整数，为所求三角形数量。

Sample Input

2 2

Sample Output

76

数据范围
1<=m,n<=1000

HINT

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