結果

問題 No.195 フィボナッチ数列の理解(2)
ユーザー codershifthcodershifth
提出日時 2015-07-12 14:43:42
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 3,897 bytes
コンパイル時間 1,708 ms
コンパイル使用メモリ 176,952 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-07-08 05:55:16
合計ジャッジ時間 2,503 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 1 ms
6,940 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 1 ms
6,944 KB
testcase_04 AC 1 ms
6,944 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 1 ms
6,940 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 1 ms
6,944 KB
testcase_09 AC 2 ms
6,940 KB
testcase_10 AC 1 ms
6,944 KB
testcase_11 AC 1 ms
6,944 KB
testcase_12 AC 1 ms
6,948 KB
testcase_13 AC 2 ms
6,944 KB
testcase_14 AC 2 ms
6,940 KB
testcase_15 AC 2 ms
6,944 KB
testcase_16 AC 2 ms
6,944 KB
testcase_17 AC 1 ms
6,944 KB
testcase_18 AC 1 ms
6,948 KB
testcase_19 AC 1 ms
6,940 KB
testcase_20 AC 1 ms
6,940 KB
testcase_21 AC 1 ms
6,940 KB
testcase_22 AC 2 ms
6,944 KB
testcase_23 AC 2 ms
6,944 KB
testcase_24 AC 1 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned long long ull;

#define FOR(i,a,b) for(int (i)=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define RANGE(vec) (vec).begin(),(vec).end()

using namespace std;

template <typename T>
void make_unique(std::vector<T> &vec) {
        std::sort(vec.begin(), vec.end());
        vec.erase(unique(vec.begin(), vec.end()), vec.end());
}

class Fibonacchi2 {
public:
    void solve(void) {
            int X,Y,Z;
            cin>>X>>Y>>Z;
            vector<int> x = {X,Y,Z};
            make_unique(x);

            //
            // Fab(k) = A*F10(k)+B*F01(k) と表現できる
            // ∵)
            // Fab(k+1) = Fab(k) + Fab(k-1)
            //          = A*F10(k)+B*F01(k) + A*F10(k-1)+B*F01(k-1)
            //          = A*(F10(k)+F10(k-1)) + B*(F01(k)+F01(k-1))
            //          = A*F10(k+1) + B*F01(k+1)
            //
            // F10(k), F01(k) を計算しておけば簡単に Fab(k) が求まる
            //
            vector<ll> F01(50);
            vector<ll> F10(50);
            F01[0] = 0;
            F01[1] = 1;
            F10[0] = 1;
            F10[1] = 0;

            // 前計算
            FOR(i, 2, 50)
            {
                F01[i] = F01[i-1] + F01[i-2];
                F10[i] = F10[i-1] + F10[i-2];
            }

            //
            // ある (p,q) にて
            // Fab(p) = A*F10(p) + B*F01(p) = X
            // Fab(q) = A*F10(q) + B*F01(q) = Y
            //
            // を満たすような (A,B) の組を見つける
            //
            vector<pair<int,int>> AB;
            // O(50*50)
            std::function<void(int, int)> solve = [&](int X, int Y) {
                REP(p, 50)
                REP(q, 50)
                {
                    int a, b, c, d;
                    a = F10[p];
                    b = F01[p];
                    c = F10[q];
                    d = F01[q];

                    int det = a*d-b*c;
                    int A = (d*X-b*Y);
                    int B = (-c*X+a*Y);
                    // 整数解が存在しないケースは飛ばす
                    if ( !det || A % det || B % det )
                        continue;
                    // 正整数のみ
                    if (A/det > 0 && B/det > 0)
                        AB.emplace_back(A/det, B/det);
                }
                make_unique(AB);
            };
            if (x.size() == 1)
            {  // A=1, B=X は明らかに解にはなるがそれが最小のものかはわからないので地道にやる
                solve(1,x[0]);
                cout<<AB[0].first<<" "<<AB[0].second<<endl;
                return;
            }
            else if (x.size() == 2)
            {
                // 2変数までなら確実に解は存在する
                solve(x[0], x[1]);
                cout<<AB[0].first<<" "<<AB[0].second<<endl;
                return;
            }
            else
            {
                // 3変数の場合は見つけた (A,B) ごとに列に Z が含まれるか確認する
                solve(x[0], x[1]);
                bool found = false;
                // Fab(p) = A*F10(p) + B*F01(p) = Z
                // O(50^3)
                for (auto ab : AB)
                {
                    int A, B;
                    tie(A,B) = ab;
                    REP(i, 50)
                    {
                        if (A*F10[i]+B*F01[i] == x[2])
                        {
                            cout<<A<<" "<<B<<endl;
                            return;
                        }
                    }
                }
                cout<<-1<<endl;
            }
    }
};

#if 1
int main(int argc, char *argv[])
{
        ios::sync_with_stdio(false);
        auto obj = new Fibonacchi2();
        obj->solve();
        delete obj;
        return 0;
}
#endif
0