3505: [Cqoi2014]數三角形

Time Limit:?10 Sec??Memory Limit:?128 MB
Submit:?478??Solved:?293
[Submit][Status]

Description

給定一個nxm的網格，請計算三點都在格點上的三角形共有多少個。下圖為4x4的網格上的一個三角形。

注意三角形的三點不能共線。

Input

輸入一行，包含兩個空格分隔的正整數m和n。

Output

輸出一個正整數，為所求三角形數量。

Sample Input

2 2

Sample Output

76


數據范圍
1<=m,n<=1000

HINT

Source

?　　這道題我居然白癡得卡在了求三點共線組數上，最開始我的想法是枚舉每一個斜率的直線，計算他們的條數與交點，但是至今我還是不知道怎么弄，正確的方法應該是枚舉三點共線兩端點的坐標差，然后可輕而易舉求出這樣的端點對數，中間點的位置數，即可解此題。

#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> using namespace std; #define MAXN 10000 typedef long long qword; int gcd(int x,int y) {return (x%y==0)?y:gcd(y,x%y); } int main() {freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout);int i,j,k,x,y,z;int n,m;scanf("%d%d",&n,&m);n++;m++;int tot=0;qword ans0,ans1=0;ans0=(qword)(m*n-2)*(m*n-1)*m*n/6;for (i=1;i<n;i++){for (j=1;j<m;j++){ans1+=(qword)(gcd(i,j)-1)*(n-i)*(m-j);}}ans1*=2;ans1+=(qword)(n-2)*(n-1)*n/6*m;ans1+=(qword)(m-2)*(m-1)*m/6*n;printf("%lld\n",ans0-ans1); }

?

轉載于:https://www.cnblogs.com/mhy12345/p/4049904.html

總結

以上是生活随笔為你收集整理的bzoj 3505: [Cqoi2014]数三角形 组合数学的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。