题目链接：HDU-5116
题意:给定若干个整数点，若一个点集满足P = {(x, y), (x + 1, y), . . . , (x + a, y), (x, y + 1), . . . , (x, y + b)}(a, b ≥ 1) 且 gcd(a, b)==1 则称这是一个好(a, b)-L集。求共有多少个(A, B)满足A，B都是好L集且A，B不相交。
思路是先找出好L集的数量a，再找出相交的好L集对数b，则答案为a * a - b 。
首先要解决的第一个问题是求出a，一个自然的思路是对于每个点，分别向右、向下搜索，但是这样做会超时。所以我们需要优化一下。
首先算出每个点向右、向下最远长度，记为rght[i][j]和down[i][j]。然后对于每个点，在向右搜索时，对于当前搜索到的长度L，我们希望能知道有多少向下的长度D可以与之组成一个好L-集。所以优化的思路就是处理出在[ 1, down[i][j] ]范围内，有多少数与L互质。我们用f[i][j]表示在[0, j]范围内有多少数与i的gcd等于1。
这样我们就解决了第一个问题。
对于第二个问题，我们处理出，对于每一个点(i, j)，有多少好L-集的下路经过点(i, j)，用sum[i][j]表示，那么假设存在x个右路经过点(i, j)的好L-集，则 b += 2 * x * sum[i][j]。
具体请参照代码：
1 //f[i][j]表示在[1,j]范围内，有多少数与i的gcd=1。 2 //g[i][j]表示在sum(gcd(a,b)==1) (1<=a<=i && 1<=b<=j) 3 //rght[i][j]表示点(i, j)右路最长长度 4 //down[i][j]表示点(i, j)下路最长长度 5 //sum[i][j]表示下路通过(i, j)的好L-集的个数 6 7 #include<cstdio> 8 #include<set> 9 #include<map> 10 #include<cstring> 11 #include<algorithm> 12 #include<queue> 13 #include<iostream> 14 using namespace std; 15 typedef long long LL; 16 17 const LL MAXN=210; 18 19 LL gcd(LL a,LL b) 20 { 21 if(b==0) return a; 22 return gcd(b,a%b); 23 } 24 bool vis[MAXN][MAXN]; 25 LL g[MAXN][MAXN],f[MAXN][MAXN],down[MAXN][MAXN],rght[MAXN][MAXN],sum[MAXN][MAXN]; 26 int main() 27 { 28 #ifdef LOCAL 29 freopen("in.txt","r",stdin); 30 #endif 31 memset(g,0,sizeof(g)); 32 memset(f,0,sizeof(f)); 33 for(LL i=1;i<=200;i++) 34 for(LL j=1;j<=200;j++) 35 { 36 f[i][j]=f[i][j-1]+(gcd(i,j)==1); 37 g[i][j]=g[i-1][j]+f[i][j]; 38 } 39 LL T; 40 scanf("%lld",&T); 41 for(LL tt=1;tt<=T;tt++) 42 { 43 memset(down,0,sizeof(down)); 44 memset(rght,0,sizeof(rght)); 45 memset(vis,0,sizeof(vis)); 46 memset(sum,0,sizeof(sum)); 47 LL n; 48 scanf("%lld",&n); 49 for(LL i=1;i<=n;i++) 50 { 51 LL x,y; 52 scanf("%lld%lld",&x,&y); 53 vis[x][y]=1; 54 } 55 for(LL i=200;i>=1;i--) 56 for(LL j=200;j>=1;j--) 57 if(vis[i][j]) 58 { 59 if(vis[i+1][j]) down[i][j]=down[i+1][j]+1; 60 if(vis[i][j+1]) rght[i][j]=rght[i][j+1]+1; 61 } 62 LL a=0; 63 memset(sum,0,sizeof(sum)); 64 for(LL i=1;i<=200;i++) 65 for(LL j=1;j<=200;j++) 66 if(vis[i][j]) 67 { 68 LL cnt[MAXN]; 69 memset(cnt,0,sizeof(cnt)); 70 for(LL k=1;k<=down[i][j];k++) 71 cnt[k]+=f[k][rght[i][j]]; 72 for(LL k=down[i][j]-1;k>=0;k--) 73 cnt[k]+=cnt[k+1]; 74 for(LL k=0;k<=down[i][j];k++) 75 sum[i+k][j]+=cnt[k]; 76 a+=cnt[0]; 77 } 78 LL b=0; 79 for(LL i=1;i<=200;i++) 80 for(LL j=1;j<=200;j++) 81 if(vis[i][j]) 82 { 83 LL cnt=0; 84 for(LL k=rght[i][j];k>=0;k--) 85 { 86 cnt+=f[k][down[i][j]]; 87 b+=2*cnt*sum[i][j+k]; 88 } 89 b-=g[down[i][j]][rght[i][j]]*g[down[i][j]][rght[i][j]]; 90 } 91 printf("Case #%lld: %lld ",tt,a*a-b); 92 } 93 return 0; 94 }