#include 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 void make_unique(std::vector &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 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 F01(50); vector 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> AB; // O(50*50) std::function 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<solve(); delete obj; return 0; } #endif