b537: 分數運算-1

內容

今天是週六，但是要上課，同學還有不少人沒來，老師在白板上寫了一個題目讓我們殺時間。

f(1)=1，對>=2 的整數 k , 若 k 為偶數則 f(k) =1+ f(k/2)，k 為奇數則 f(k) = 1/f(k-1)， 問 f(k) = 30/11 時，k 為多少？

輸入

每組測資有多列以 EOF 結束，每列兩個正數數 a,b 代表 f(k)的值 a/b， 1<= a,b <= 60 ，a 及 b 以空白隔開

1 1
2 1
1 2
3 1
1 3
3 2
2 3
4 1
1 4
4 3
30 11

輸出

對每一列輸入的 a , b 輸出一列，為一個正整數 k，使 f(k) = a/b

1
2
3
4
5
6
7
8
9
10
236

解題思路

情況觀察:

當 k 為 1 時 f(k) = 1 → f(k) = 1

當 k 為偶數時 f(k) = f(k/2) + 1 → ，f(k) > 1

當 k 為奇數時 f(k) = 1 / f(k-1) → ，f(k) < 1

發現可以用 1 和 f(k) 比較來判斷 k 的奇偶，也能透過此方法推出 k 是透過哪個式子轉化成 f(k)。

可以判斷是來自哪種式子的話就可以反推原本的輸入。

當 g(k) = N 時 → g(k) = 2^k-1 (N 代表整數)

當 g(k) > 1 時 → g(k) = (g(k) + 1) * 2^floor(k)

當 g(k) < 1 時 → g(k) = g(1/k) + 1

再把 k 轉換成題目給的 a 和 b

當 a = b 時 → g(k) = 2^(a/b)-1

當 a > b 時 → g(k) = (g(a/b) + 1) * 2^floor(a/b)

當 a < b 時 → g(k) = g(b/a) + 1

用遞迴套用公式就可以逆推回剛開始的數字(答案)了。

完整程式碼

AC (2ms, 68KB)

#include <stdio.h>

long long getK(int a, int b)
{
    if (b < a)
    {
        int shift = a / b;
        a %= b;
        return a ? (getK(b, a) + 1) << shift : 1LL << (shift - 1);
    }
    else
    {
        return a == b ? 1 : getK(b, a) + 1;
    }
}

int main()
{
    int a, b;
    while (scanf(" %d %d", &a, &b) == 2)
    {
        printf("%lld\n", getK(a, b));
    }
    return 0;
}