可憐的小貓負責做苦工。
假設第一隻貓的身高為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++;
}
}
