棋盘（数学趣味题） - HDU 5100

Problem Description

Consider the problem of tiling an n×n chessboard by polyomino pieces that are k×1 in size; Every one of the k pieces of each polyomino tile must align exactly with one of the chessboard squares. Your task is to figure out the maximum number of chessboard squares tiled.

对于一个n*n大小的棋盘，放入k*1大小的长方形，放入后需要对齐（也就是说不考虑浮点型位置）。

求能放入的最大面积。

Input

There are multiple test cases in the input file.

First line contain the number of cases T (T≤10000).

In the next T lines contain T cases , Each case has two integers n and k. (1≤n,k≤100)

输入T，表示有T个用例

每个用例输入棋盘大小n和长方形的长k。

Output

Print the maximum number of chessboard squares tiled.

Sample Input

2

6 3

5 3

Sample Output

36

24

这是一个数学题，对于每个k，有两种不同的放置方法。

1. 先横着摆放，然后用竖着的补全，剩下的是一个边长为n%k的正方形
2. 在一个角摆成风车形（边长k+n%k），中间形成边长为k-n%k的正方形

（方法1 先横着后竖着）

（方法2 摆成风车型）

比如对于5和3来说，如果采用方法1，那么剩下的方形边长是2，采用方法2，剩下的方形边长是1。

源代码：G++ 0ms

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int main() {
    int test_count;
    scanf("%d", &test_count);

    while (test_count--)
    {
        int n, k;
        scanf("%d%d", &n, &k);

        if (k > n)
            puts("0");
        else {
            if (n % k == 0)
                printf("%d\n", n * n);
            else {
                //两种摆法取边小的
                //1、横着摆放竖着补全，形成边长n%k的正方形 
                //2、在一个角摆成风车形（边长k+n%k），中间形成边长为k-n%k的正方形
                int m = min(n % k, k - n % k);
                printf("%d\n", n * n - m*m);
            }
        }
    }
    return 0;
}