数三角形 (Counting Triangles,Dhaka 2005,LA 3295)

 1 #include <iostream>
 2 #include <string.h>
 3 #include <string>
 4 #include <fstream>
 5 #include <algorithm>
 6 #include <stdio.h>
 7 #include <vector>
 8 #include <queue>
 9 #include <set>
10 #include <cmath>
11 using namespace std;
12 const double eps = 1e-8;
13 const int INF=0x7fffffff;
14 unsigned long long uINF = ~0LL;
15 #define MAXN 10000007
16 typedef long long LL;
17 LL gcd(LL a,LL b)
18 {
19     return b==0?a:gcd(b,a%b);
20 }
21 LL g[1001][1001];
22 void init()
23 {
24     for(int i=1;i<=1000;i++)
25         for(int j=1;j<=1000;j++)
26         g[i][j]=gcd(i,j);
27 }
28 int main()
29 {
30     LL n,m;int t=1;
31     init();
32     while(scanf("%lld%lld",&n,&m),n+m)
33     {
34         LL sum=n*m+n+m+1;
35         sum=sum*(sum-1)*(sum-2)/6;
36         LL x=(n+1)*n*(n-1)/6*(m+1);
37         LL y=(m+1)*m*(m-1)/6*(n+1);
38         LL ans=0;
39         for(int i=2;i<=n;i++)
40             for(int j=2;j<=m;j++)
41             ans+=(g[i][j]-1)*(n-i+1)*(m-j+1);
42 
43             ans*=2;
44         printf("Case %d: %lld
",t++,sum-x-y-ans);
45     }
46 
47     return 0;
48 }

网格点数所有三元组然后排除共线的三元组

和 LA3720 一样枚举斜率 ~