大神的世界

想法:

因為f(1) = 1 > 0

故，f(n)恆正 (n 須為正整數)

接著，我們假設題目給的數字為第k項

k是多少，我們不知道

但我們知道 f(1) = 1

故，我們可將f(k)的值回推

怎麼推呢?

前面我們有一個很重要的結論

就是f(n)恆為正數

是故，當f(k) < 1時，k絕不可能是偶數

否則 f(k/2) 會是負的

於是我們得出以下結論

1.若f(k) > 1 則k為偶數

2.若f(k) < 1 則k為奇數

接著，當k為偶數時，f(k) = 1 + f(k/2)

將1移到左邊

=> f(k) - 1 = f(k/2)

這個式子是有意義的

它在告訴我們，若把f(k) - 1 就相當於把 自變數(k) 除以2

接著，當k為奇數時，f(k) = 1 / f(k - 1)

它在告訴我們，若把f(k) 取倒數 就相當於把 自變數(k) -1

因此，我們只要不斷重複以上步驟，那麼k的值就會逐漸減少

最後，當f(k) = 1時，此時的k值就會等於1

接下來我們只要將 除2 變 乘2  ， -1 變 +1  就能反求原來的k值

若聽不太清楚，下面我舉個例子

試問: 3 / 14 是第幾項?? (此處用---->表示"來自於")

3 / 14   ----> 14 / 3 ----> 11 / 3 ----> 8 / 3 ----> 5 / 3 ----> 2 / 3 ----> 3 / 2 ----> 1 / 2 ----> 2 / 1 ----> 1 / 1 

k 的運算:  -1   /2   /2   /2   /2   -1   /2   -1   /2    此時k = 1

回推k值:  1 -> 2  ->  3  ->  6  ->  7  ->  14  ->  28  ->  56  ->  112  ->  113

=>第 113 項

這樣懂嗎??

以下程式碼為當初觀察計算得到的結果

當f(n)為整數時，n的值會等於 2^( f(n) - 1)

不難推，麻煩自理

迴圈

輸入a b

先求其最簡分數

迴圈( 若 a/b 不是整數)

若a > b

放入a/b (代表減了a/b個1)

否則

交換a b

放入 0 (等等就知道為什麼了)

設定第n項的值

當f(n)為整數時，n的值會等於 2^( f(n) - 1)

回推n的值

輸出n

#include <iostream>
#include <cmath>
#include <algorithm>
#include <stack>

using namespace std;

int main()
{
    unsigned long long int a, b, n;
    int gcd;
    stack <int> op;

    while(cin >> a >> b)
    {
        gcd = __gcd(a,b);
        a/=gcd, b/=gcd;

        while(a % b)
        {
            if(a>b)
            {
                op.push(a/b);
                a%=b;
            }

            swap(a, b);
            op.push(0);
        }

        n = pow(2, a/b-1);

        while(!op.empty())
        {
            if(op.top() > 0)
                n*=pow(2, op.top());
            else
                n++;

            op.pop();
        }

        cout << n << endl;
    }

    return 0;
}