【待完善】UVA-11538：Chess Queen

Chess Queen

来源：UVA

标签：数论

参考资料：

相似题目：

题目

Most people are familiar with how chess is played and how a queen operates within the game. Two queens are considered to be in an attacking position if they share the same row, column, or diagonal on the chessboard. Imagine placing two queens, one black and one white, on a 2×2 chessboard. There are 12 distinct configurations where this occurs, illustrated below.

Consider an (N × M) board; you must determine the number of ways two queens can occupy attacking positions on it.

输入

输入文件最多可容纳5000条输入数据。

每条记录包含两个非负整数M和N（其中M和N均大于等于1且小于等于1e6）。

输入将由一个包含两个零的行来终止。

这两个零不需要被处理。

输出

For each line of input, generate a corresponding output line. This output line includes an integer that represents the number of ways two queens can attack each other on a (M×N) chessboard, where M and N are derived from the input. All output values are within the range of a 64-bit signed integer.

输入样例

2 2
100 223
2300 1000
0 0

输出样例

12
10907100
11514134000

解题思路

总方案数由所有行、列及对角线上的独立方案数量之和构成。每一行具有n(n-1)种独立方案（即排列数A(n,2)），共有m行，则所有行上的独立方案总数为mn(n-1)种。由于行列结构对称性相同，则所有列上的独立方案数目计算方式与行相同。在m×n的棋盘上，主次对角线的长度依次为1、2、3一直到m-1、m；而对于副次对角线则长度依次为m、m、…、一直到2、1（共计有n−m+1个长度为m的主次对角线）。由于每条主次对角线上都存在两种不同的方向取向，则最终结果需乘以2。

参考代码（AC）

    #include<stdio.h>
    int main(){
    	long long m,n;//m:row, n:col
    	while(scanf("%lld%lld",&m,&n) && m){
    		unsigned long long ans=0;
    		if(m>n){
    			unsigned long long t=m;
    			m=n;
    			n=t;
    		}
    		ans+=m*n*(n-1);//row 
    		ans+=n*m*(m-1);//col 
    		ans+=2*m*(m-1)*(3*n-m-1)/3;//diagonal
    		printf("%lld\n",ans);
    	}
    	return 0;
    }

参考代码（WA）

    #include<stdio.h>
    int main(){
    	int m,n;//m:row, n:col
    	while(scanf("%d%d",&m,&n) && m){
    		unsigned long long ans=0;
    		if(m>n){
    			int t=m;
    			m=n;
    			n=t;
    		}
    		ans+=m*n*(n-1);//row 
    		ans+=n*m*(m-1);//col 
    		ans+=2*m*(m-1)*(3*n-m-1)/3;//diagonal
    		printf("%lld\n",ans);
    	}
    	return 0;
    }