Luogu P3166 [CQOI2014]数三角形组合数学

好题鸭。。

不好直接求三角形个数，那就用全集-补集，转化为求三点共线的数量。

具体求法是求出水平共线数量与竖直共线数量和斜线共线数量。

用排列组合的知识可知为水平和竖直的为$C_n^3$与$C_m^3$。

求斜线三点共线：显然，对于点$(a,b) (x,y)$连成的线段$(其中a>x,b>y)$，在它们中间有$gcd(a-x,b-y)-1$个整点，因此基本的思路就是枚举两个点，然后第3个点就是$gcd(a-x,b-y)-1$种可能了。我们又发现，这些线段是可以平移和对称（/和\）的，于是并不需要枚举所有的两个点，只用枚举$(0,0)$和$(x,y)$，然后通过平移和对称（$*2$）来计算出现的次数。

那么可以发现，这样任意一条线，向上只能平移$(n-i)$，向下$(m - j)$次，

所以出现次数就为$(n - i + 1) * (m - j + 1)$,其中$+1$是因为可以不移动

#include<iostream>

#include<cstdio>

#define ll long long

#define R register ll

using namespace std;

inline int g() {

    R ret=,fix=; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-:fix;

    do ret=ret*+(ch^); while(isdigit(ch=getchar())); return ret*fix;

}

int n,m;

ll ans;

inline int gcd(int a,int b) {return b?gcd(b,a%b):a;}

signed main() {

    n=g()+,m=g()+; ans=1ll*n*m;

    ans=1ll*ans*(ans-)*(ans-)/-1ll*m*n*(n-)*(n-)/-1ll*n*m*(m-)*(m-)/;

    for(R i=;i<n;++i) for(R j=;j<m;++j) ans-=1ll**(gcd(i,j)-)*(n-i)*(m-j);

    printf("%lld\n",ans);

}

2019.06.01

巴特西

Luogu P3166 [CQOI2014]数三角形组合数学

最新文章

热门文章

巴特西

Luogu P3166 [CQOI2014]数三角形 组合数学

最新文章

热门文章

Luogu P3166 [CQOI2014]数三角形组合数学