正題

題目鏈接:https://www.luogu.com.cn/problem/P3166

---

題目大意

求一個$N?M$的網格上有多少個三角形。

---

解題思路

考慮減去共線的情況，我們分為兩種情況。一是平行于坐標軸的，這個很好算。二是傾斜的，我們考慮如何計算斜下角的。

首先我們可以枚舉一個點作為左上角的點$(x,y)$，對于一個在它右下角的點$(x+a,y+a)$在他們中間有$gcd(a,b)$個點和它們共線。當然除了$gcd(1,1)=1$的情況要減去。預處理$gcd$的二維前綴和就可以了。

時間復雜度$O(nm)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=1100; ll n,m,g[N][N],ans; ll gcd(ll x,ll y){if(!y)return x;if(g[x][y])return g[x][y];return gcd(y,x%y); } int main() {scanf("%lld%lld",&n,&m);n++;m++;for(ll i=1;i<=n;i++)for(ll j=1;j<=m;j++)g[i][j]=gcd(i,j);for(ll i=1;i<=n;i++)for(ll j=1;j<=m;j++)g[i][j]+=g[i-1][j]+g[i][j-1]-g[i-1][j-1]-1;for(ll i=1;i<=n;i++)for(ll j=1;j<=m;j++){ans+=g[n-i][m-j];}ll k=n*m;printf("%lld",k*(k-1)*(k-2)/6-ans*2-m*n*(n-1)*(n-2)/6-n*m*(m-1)*(m-2)/6); }

總結

以上是生活随笔為你收集整理的P3166-[CQOI2014]数三角形【GCD】的全部內容，希望文章能夠幫你解決所遇到的問題。

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