http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=99&page=show_problem&problem=1731 這是一個(gè)數(shù)學(xué)題，比較有意思。題意大致是：有2條平行的直線(xiàn)，第一條上面有m個(gè)點(diǎn)，第二條上面有n個(gè)點(diǎn)。那么連接這寫(xiě)點(diǎn)能產(chǎn)生m*n
條直線(xiàn)(不包括和原來(lái)的執(zhí)行平行的直線(xiàn))。問(wèn)這m*n直線(xiàn)最多有多少個(gè)內(nèi)交點(diǎn)(意思是不屬于原來(lái)m,n個(gè)點(diǎn)的交點(diǎn))...
想來(lái)想去，推理了1個(gè)多小時(shí)才出來(lái)正式結(jié)果。感覺(jué)比較有意思，寫(xiě)篇博文記錄下。我先是從反面排除，想了試了好久到最后還是發(fā)現(xiàn)無(wú)法
排除干凈。。。最后只能從正面開(kāi)始求證了。我這樣定義一條執(zhí)行(i，j)，其中i代表在第一條直線(xiàn)中的端點(diǎn)，j代表在第二條直線(xiàn)中的端點(diǎn)。
顯然1 <= i <= m，而且1 <= j <= n。
現(xiàn)在的話(huà)只要求出和直線(xiàn)(i，j)相加的直線(xiàn)有多少條，然后對(duì)i，j進(jìn)行累加求和。再對(duì)和除以2就能得到答案了。
那么有多少條直線(xiàn)能和直線(xiàn)(i，j）相交了。很顯然，和(i,j)相交的直線(xiàn)的端點(diǎn)必須在其兩側(cè)。意思是在第一條直線(xiàn)中的端點(diǎn)范圍為
[1, i - 1],在第二條直線(xiàn)中的端點(diǎn)范圍為[j + 1, n]，總結(jié)(i - 1) * (n - j) 條直線(xiàn)。但是還有第二種情況,在第一條直線(xiàn)中的端點(diǎn)范圍
為[i + 1, m], 在第二條直線(xiàn)中的端點(diǎn)范圍為[1, j - 1]，總結(jié)(m - i) * (j - 1) 條直線(xiàn)。
總計(jì)sum = i * n + i - m -n + j (m - 2 * i + 1) 條直線(xiàn)。
再求
Σsum（j從1到n)得到和式(m*n*n - m*n - n*n + n) / 2，再對(duì)這個(gè)式子進(jìn)行i從1到m的累加。因?yàn)闆](méi)有i了，其效果就是乘以m。
然后最終的和除以2，所以最后的表達(dá)式是(m*m*n*n - m*m*n - m*n*n + m*n) / 4。這個(gè)式子顯然是關(guān)于m,n對(duì)稱(chēng)的。
這一點(diǎn)也可以驗(yàn)證這個(gè)式子的正確性。
程序?qū)懫饋?lái)就很簡(jiǎn)單了，代碼如下：
#include <iostream>
using namespace std;
int main()
{
long long m, n;
int nCases = 0;
while (cin >> m >> n, m + n != 0)
{
long long a = m * m;
long long b = n * n;
cout << "Case " << ++nCases << ": "
<< (a * b - a * n - b * m + m * n) / 4 << endl;
}
return 0;
}