$Description$
给定一个 $n times m$ 的网格,请计算三点都在格点上的三角形共有多少个。
$Solution$
考虑分类讨论。
首先,我们发现,每个顶点都在格点上的三角形能且只能被一个矩形完全包含,也就是
而下面这个当中的大矩形就是不包含这个下图中的三角形的,只有用红色标出的小矩形才包含。
所以就将问题转化成了求子矩形个数。
显然,长为 $i$ ,宽为 $j$ 的子矩形有 $(m - i + 1) times (n - j + 1)$ 个。
然后考虑一个子矩形中有多少种可能的三角形个数。
我们考虑固定一个端点,移动其他两个端点:
红色的点表示固定的点,也就是 $A$ 点,绿色的线表示 $B$ 点此时的活动范围,橙色的线表示 $C$ 点此时的活动范围。
显然, $A$ 点有 $4$ 种方案, $B$ 点有 $i - 1$ 种方案, $C$ 点有 $j - 1$ 种方案。
所以方案数就是 $4 times (i - 1) times (j - 1)$
然后我们考虑处在顶点上的特殊情况,我们钦定 $B$ 与顶点重合。
当 $B$ 与左上角端点重合时, $C$ 就只能在右边的一条边上动,就有 $i - 1$ 种情况。
当 $B$ 与右下角端点重合时, $C$ 就只能在上面的一条边上动,就有 $j - 1$ 种情况。
当 $B$ 与右上角端点重合时,情况就变得复杂了。
可以发现此时 $A to B$ 不仅仅经过了左下角与右上角两个端点,还经过了中间的一些格点,手玩一下几个数据可以发现,经过的格点数是 $gcd(i, j) - 1$ 个。
所以,方案个数就是 $(i + 1) times (j + 1) - 4 - (gcd(i, j) - 1)$ 。
注意此处图形可以翻转,所以答案要乘二。
所以,对于每个子矩阵,完全覆盖的三角形个数就是 $$ 4 times (i - 1) times (j - 1) + 2 times [(i - 1) + (j - 1) + (i + 1) times (j + 1) - 4 - (gcd(i, j) - 1)] $$ 化简后就是 $$ 6 times i times j - 2 times gcd(i, j) $$
$Code:$
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63
#define ls(x) ( x << 1 ) #define rs(x) ( x << 1 | 1 ) #define lowbit(x) ( x & -x ) #define debug(x) (cout << "#x = " << x << endl) #define re register #define For(i, j, k) for(re int i = (j); i <= (k); i++) #define foR(i, j, k) for(re int i = (j); i >= (k); i--) #define Cross(i, j, k) for(re int i = (j); i; i = (k)) using namespace std ;typedef long long ll;const ll N = 100011 ;const ll inf = 0x3f3f3f3f3f3f ;ll m, n, ans = 0 ; namespace IO { #define dd ch = getchar() inline ll () { ll x = 0 ; bool f = 0 ; char dd; for (; !isdigit (ch); dd) f ^= (ch == '-' ); for (; isdigit (ch); dd) x = (x << 3 ) + (x << 1 ) + (ch ^ 48 ); return f? -x: x; } #undef dd inline void write ( ll x ) { if ( x < 0 ) putchar ( '-' ), x = -x; if ( x > 9 ) write ( x / 10 ); putchar ( x % 10 | 48 ); } inline void wrn ( ll x ) { write (x); putchar ( ' ' ); } inline void wln ( ll x ) { write (x); putchar ( 'n' ); } inline void wlnn ( ll x, ll y ) { wrn (x), wln (y); } } using namespace IO;inline ll gcd ( ll a, ll b ) { return !b? a: gcd (b, a % b); }int main () { m = read(), n = read(); For ( i, 1 , m ) For ( j, 1 , n ) ans += ( m - i + 1 ) * ( n - j + 1 ) * ( 6 * i * j - 2 * gcd (i, j) ); return wln (ans), 0 ; }
题目链接
近期评论