tkdsheep-solution-0005

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
Pi学姐的神题

比赛的时候主要是不知道gcd的结论，然后自己yy了好多种错误的公式。。。

先算任选三点的方案数

减掉水平、竖直的方案数

然后减掉“斜着”的三点共线情况即可，这里我的做法是这样的：

三点共线肯定是一条线段，然后线段中间多出一个点，所以就以原点(0,0)为线段的一个端点，枚举另一个端点(i,j)

注意i和j不能为0，否则就是水平或竖直了

那么中间那个点的选择方案数就是gcd(i,j)-1

然后这条线段可以往右、往上平移，计算这些情况，最后乘2，因为对角线有2条

}}}

Pi学姐的神题
比赛的时候主要是不知道gcd的结论，然后自己yy了好多种错误的公式。。。
先算任选三点的方案数
减掉水平、竖直的方案数
然后减掉“斜着”的三点共线情况即可，这里我的做法是这样的：
三点共线肯定是一条线段，然后线段中间多出一个点，所以就以原点(0,0)为线段的一个端点，枚举另一个端点(i,j)
注意i和j不能为0，否则就是水平或竖直了
那么中间那个点的选择方案数就是gcd(i,j)-1
然后这条线段可以往右、往上平移，计算这些情况，最后乘2，因为对角线有2条