顯然可以用總方案數(shù)減掉三點(diǎn)共線的情況。對(duì)于三點(diǎn)共線，一個(gè)暴力的做法是枚舉起點(diǎn)終點(diǎn)，其間整點(diǎn)數(shù)量即為橫縱坐標(biāo)差的gcd-1。這樣顯然會(huì)T，注意到起點(diǎn)終點(diǎn)所形成的線段在哪個(gè)位置是沒有區(qū)別的，于是枚舉線段算出這樣的線段條數(shù)就可以了。

　　似乎可以莫比烏斯反演一波。

#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; int read() {int x=0,f=1;char c=getchar();while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f; } #define ll long long int n,m; ll ans; ll C(int x,int y){return 1ll*x*(x-1)*(x-2)/6;} int gcd(int n,int m){return m==0?n:gcd(m,n%m);} int main() { #ifndef ONLINE_JUDGEfreopen("bzoj3505.in","r",stdin);freopen("bzoj3505.out","w",stdout);const char LL[]="%I64d\n"; #elseconst char LL[]="%lld\n"; #endifn=read(),m=read();ans=C((n+1)*(m+1),3);for (int i=0;i<=n;i++)for (int j=0;j<=m;j++)if (i|j) ans-=1ll*(n+1-i)*(m+1-j)*(gcd(i,j)-1)<<(i&&j);cout<<ans;return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Gloid/p/9536184.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ3505 CQOI2014数三角形（组合数学）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。