ACM 107 The Cat in the Hat

可憐的小貓負責做苦工。
假設第一隻貓的身高為H，
需要作工的的貓數量為W。

一開始，貓的數量1，貓的身高H，
叫貓一次之後，
貓的數量共1 + N，
貓的總身高H + H * N / (1 + N)。
叫貓第二次，
貓的數量共1 + N + N ^ 2，
貓的總身高H + H * N / (1 + N) + H * N^2 / (1 + N) ^ 2。
叫貓第三次，
貓的數量共1 + N + N ^ 2 + N ^ 3，
貓的總身高H + H * N / (1 + N) + H * N^2 / (1 + N) ^ 2 + H * N^3 / (1 + N) ^ 3。
叫貓第k次，
貓的數量共1 + N + N ^ 2 + N ^ 3 + ... + N ^ k，
貓的總身高H + H * N / (1 + N) + H * N^2 / (1 + N) ^ 2 + H * N^3 / (1 + N) ^ 3 + ... + H * N^k / (1 + N) ^ k。

第k次的貓，身高為H / (1 + N) ^ k，數量為N ^ k，
根據題目說明，此貓身高為1，數量為W：
(1)1 = H / (1 + N) ^ k，所以H = (1 + N) ^ k，
(2)W = N ^ k。

由等比級數公式[1 - r^(k+1)] / 1 - r可得。（公比為r）
貓的數量：[1 - N^(k+1)] / (1 - N)，
不用作工貓的數量，就是算到k-1次的意思：
{[1 - N^(k-1 + 1)] / (1 - N)}
展開化簡：
(3)(1 - W) / (1 - N)。

全部的貓身高加總
H + H * N / (1 + N) + H * N^2 / (1 + N) ^ 2 + H * N^3 / (1 + N) ^ 3 + ... + H * N^k / (1 + N) ^ k，
H * [1 + N / (1 + N) + N^2 / (1 + N) ^ 2 + N^3 / (1 + N) ^ 3 + ... + N^k / (1 + N) ^ k]，
（忽然想學LaTex，要不然這樣打數學公式實在有夠辛苦）
反正[]內的東西是等差級數，我直接寫化簡結果：
(4)H * (N + 1) - W * N。
（用H、W代入就可以化簡）

由(3)(4)可知只要知道N，就能計算偷懶貓與總貓身高了。
那N怎麼求呢？
H = (1 + N) ^ k
W = N ^ k
可以知道存在唯一N使得此N的k次方跟(1+N)的k次方為W、H。
所以N從2開始往上代，只要滿足
N跟N + 1對W、H取餘數為0，
滿足的話，就計算W /= N、H /= N + 1，再取餘數，再/=，
反覆到W == 1跟N == 1為止。
若取餘數不為0，或不滿足W == 1跟N == 1，
N++往上代。

話說這裡想好久，囧，同時算H、W，
比先算其中一個再算另一個還快。

另外公式的部份要注意N = 1會讓分母為0（害我一直RE），
所以N = 1的情況要特別處理。（即W = 1的情況）

2011/11/08 update:
幫人檢查code，發現到
原來H跟W差1的情況下，
N就是W。
例如：30 29
N為29
答案就是1 59(30 + 29)。
Code可以改寫囉！ 

/* ACM 107
 * mythnc
 * 2011/10/17 19:16:52   
 * run time: 0.064
 */
#include <stdio.h>

int findn(int, int);

int main(void)
{
    int w, h, n;

    while (scanf("%d %d", &h, &w) == 2) {
        if (!h && !w)
            break;
        if (h == 1) {
            printf("0 1\n");
            continue;
        }
        if (w == 1) {
            while ((h >> w) != 1)
                w++;
            printf("%d %d\n", w, 2 * h - 1);
            continue;
        }
        n = findn(h, w);
        printf("%d %d\n", (w - 1) / (n - 1), (n + 1) * h - w * n);
    }
    return 0;
}

/* findn: find and return the constant N */
int findn(int h, int w)
{
    int n, i, j;

    n = 2;
    while (1) {
        i = w;
        j = h;
        /* n have to divide w and j */
        while (i % n == 0 && j % (n + 1) == 0) {
            i /= n;
            j /= n + 1;
            if (i == 1 && j == 1)
                return n;
        }
        n++;
    }
}