結果

問題 No.195 フィボナッチ数列の理解(2)
コンテスト
ユーザー codershifth
提出日時 2015-07-12 14:43:42
言語 C++11（廃止可能性あり）
(gcc 13.3.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

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