3505: [Cqoi2014]數三角形

Time Limit: 1 Sec??

Memory Limit: 256 MB

題目連接

http://www.lydsy.com/JudgeOnline/problem.php?id=3505

Description

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

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

Input

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

Output

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

Sample Input

2 2

Sample Output

76

HINT

1<=m,n<=1000

題意

?

題解：

任意選擇三個不在同一條直線上的三個點即是滿足題意的點

考慮補集，隨意選擇3個點，然后刪除同一直線，同一斜線的就好了

直線上的比較簡單，只用想斜線的就好了

枚舉矩形，矩形的長寬分別為i,j，那么這個矩形的對角線就會經過gcd(i,j)-1個點

然后這個圖里面可以放(n-i+1)*(m-j+1)個矩形

然后搞一搞就好了

代碼：

//qscqesze #include <cstdio> #include <cmath> #include <cstring> #include <ctime> #include <iostream> #include <algorithm> #include <set> #include <bitset> #include <vector> #include <sstream> #include <queue> #include <typeinfo> #include <fstream> #include <map> #include <stack> typedef long long ll; using namespace std; //freopen("D.in","r",stdin); //freopen("D.out","w",stdout); #define sspeed ios_base::sync_with_stdio(0);cin.tie(0) #define maxn 510000 #define mod 10007 #define eps 1e-9 int Num; //const int inf=0x7fffffff; //§?§é§à§é¨f§3 const int inf=0x3f3f3f3f; inline ll read() {ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f; } //************************************************************************************** ll gcd(ll a,ll b) {return b==0?a:gcd(b,a%b); } int main() {ll n=read(),m=read();n++,m++;ll ans = (n*m)*(n*m-1)*(n*m-2LL)/6LL;ans -= n*(m*(m-1LL)*(m-2LL)/6LL);ans -= m*(n*(n-1LL)*(n-2LL)/6LL);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){ll tmp = gcd(i,j)+1LL;if(tmp>2LL)ans-=(tmp-2LL)*2LL*(n-i*1LL)*(m-j*1LL);}}printf("%lld\n",ans); }

?

轉載于:https://www.cnblogs.com/qscqesze/p/4776095.html

總結

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

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