3505: [Cqoi2014]數三角形
Time Limit:?10 Sec??Memory Limit:?128 MBSubmit:?698??Solved:?424
[Submit][Status][Discuss]
Description
給定一個nxm的網格，請計算三點都在格點上的三角形共有多少個。下圖為4x4的網格上的一個三角形。
注意三角形的三點不能共線。
Input
輸入一行，包含兩個空格分隔的正整數m和n。
Output
輸出一個正整數，為所求三角形數量。
Sample Input
2 2
Sample Output
76
數據范圍
1<=m,n<=1000
數據范圍
1<=m,n<=1000
HINT
ans=任取三個點的方案?三點在同一條直線的方案
任取三點的方案=((n+1)?(m+1)3)
三點在同一條直線的方案=水平的+豎直的+斜著的=(n+1)?(m+13)+(m+1)?(n+13)+斜著的
斜著的怎么算呢？
算出“\”的，“/”用“\”乘2即可。
我們枚舉i，j表示這條斜著的線的端點分別是i?j的矩形的左上角和右下角，這條斜線兩點已經確定，這條斜線與格點的交點個數為：gcd(i,j)?1?
（把斜線當做直角三角形的斜邊就明白為什么是gcd(i,j)?1了）
而這條斜線還可以平移，一共有(n+1?i)?(m+1?j)條，最后這樣的斜線一共有
(gcd(i,j)?1)?(n+1?i)?(m+1?j)
條，就可以算了。
?
 - 反射)
)
