結果

問題 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,547 ms
コンパイル使用メモリ 162,284 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-22 14:19:27
合計ジャッジ時間 2,800 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 2 ms
4,376 KB
testcase_09 AC 1 ms
4,376 KB
testcase_10 AC 1 ms
4,380 KB
testcase_11 AC 2 ms
4,380 KB
testcase_12 AC 2 ms
4,380 KB
testcase_13 AC 2 ms
4,380 KB
testcase_14 AC 2 ms
4,380 KB
testcase_15 AC 2 ms
4,376 KB
testcase_16 AC 1 ms
4,380 KB
testcase_17 AC 2 ms
4,376 KB
testcase_18 AC 1 ms
4,380 KB
testcase_19 AC 2 ms
4,376 KB
testcase_20 AC 2 ms
4,380 KB
testcase_21 AC 1 ms
4,380 KB
testcase_22 AC 1 ms
4,380 KB
testcase_23 AC 1 ms
4,376 KB
testcase_24 AC 1 ms
4,376 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