移动端网站怎么提交,防城港装修公司口碑排行,什么软件网站好,做企业网站制作正题
题目链接:https://www.luogu.com.cn/problem/P3166 题目大意
求一个N∗MN*MN∗M的网格上有多少个三角形。 解题思路
考虑减去共线的情况#xff0c;我们分为两种情况。一是平行于坐标轴的#xff0c;这个很好算。二是倾斜的#xff0c;我们考虑如何计算斜下角的。
…正题
题目链接:https://www.luogu.com.cn/problem/P3166 题目大意
求一个N∗MN*MN∗M的网格上有多少个三角形。 解题思路
考虑减去共线的情况我们分为两种情况。一是平行于坐标轴的这个很好算。二是倾斜的我们考虑如何计算斜下角的。
首先我们可以枚举一个点作为左上角的点(x,y)(x,y)(x,y)对于一个在它右下角的点(xa,ya)(xa,ya)(xa,ya)在他们中间有gcd(a,b)gcd(a,b)gcd(a,b)个点和它们共线。当然除了gcd(1,1)1gcd(1,1)1gcd(1,1)1的情况要减去。预处理gcdgcdgcd的二维前缀和就可以了。
时间复杂度O(nm)O(nm)O(nm) codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N1100;
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 i1;in;i)for(ll j1;jm;j)g[i][j]gcd(i,j);for(ll i1;in;i)for(ll j1;jm;j)g[i][j]g[i-1][j]g[i][j-1]-g[i-1][j-1]-1;for(ll i1;in;i)for(ll j1;jm;j){ansg[n-i][m-j];}ll kn*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);
}
