用边长为2^K, 2^(K-1), ..., 4, 2, 1的正方形填充一个M x N的矩形

Question

我们有一个 M x N 的矩形，需要用边长为 2^K, 2^(K - 1), ..., 4, 2, 1 的正方形来填充它。我们先用尽可能多的 2^K 填充，然后用 2^(K - 1)，以此类推。总共需要多少个正方形呢？

我编写了以下递归代码：

#include <stdio.h>
#include <stdlib.h>

long long_pow(long base, long exponent)
{
    if (!exponent)
        return 1L;

    return base * long_pow(base, exponent - 1L);
}

long cover(long width, long height, long side)
{
    if (width <= 0L || height <= 0L)
        return 0L;

    long full_width = width / side;   // The full width we can cover.
    long full_height = height / side; // The full height we can cover.

    return (full_width * full_height) // The full area we can cover
                                      // plus the rest (recursively).
           + cover(width - full_width * side, height, side / 2L)
           + cover(full_width * side, height - full_height * side, side / 2L);
}

int main()
{
    long width, height, k;
    scanf("%ld %ld %ld", &width, &height, &k);
    printf("%ld\n", cover(width, height, long_pow(2L, k)));
    return 0;
}

这段代码在我收到的10个测试用例中有1个不通过。具体来说，对于123456789 987654321 4，它输出了1690311532而非正确答案476300678536044。然而，在123456789 987654321 30上，它输出了正确答案1437797319。其他测试用例也表现良好。

问题可能出在哪里？

- d125q

---

我运行了它，并且对于测试用例 123456789 987654321 4 给出了正确的结果，即：476300678536044。 - syntagma

@REACHUS：非常感谢。问题是我的系统上的long不够长。将所有内容替换为uint64_t就解决了。 - d125q

Answer 1

代码唯一的问题是 long 溢出了。我使用了 unit64_t 代替。

- d125q