[题解]（组合数学/gcd）luogu

首先转化为ans=所有的组合方式 - 在同一水平/竖直线上 - 在同一斜线上

主要考虑在同一斜线上的情况

首先想到枚举斜率然后在坐标系内平移，以(0,0)为起点，每条线上的点数应该是gcd(x,y)比较好理解

所以在这条线段上有gcd(x,y)-1个选择方式（已选(0,0)、(x,y)）

可向下/右移动的空间是 n-x、m-y比较显然，所以都乘起来即为贡献

#include<iostream>

#include<cstdio>

#include<cstring>

#define ll long long

using namespace std;

const int maxn=;

ll m,n;

int main(){

    scanf("%lld%lld",&m,&n);m++,n++;

    ll s=m*n;

    ll ans=s*(s-)*(s-)/;

    for(int x=;x<=n;x++)

    for(int y=;y<=m;y++){

        if(x||y){

            if(!x||!y)ans-=(gcd(x,y)-)*(n-x)*(m-y);//水平/豎直

            else ans-=*(gcd(x,y)-)*(n-x)*(m-y);

        }

    }

    printf("%lld",ans);

}

巴特西

[题解]（组合数学/gcd）luogu_P3166数三角形

最新文章

热门文章