結果

問題 No.195 フィボナッチ数列の理解(2)
ユーザー koyumeishikoyumeishi
提出日時 2015-05-26 00:17:33
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 2,681 bytes
コンパイル時間 713 ms
コンパイル使用メモリ 86,604 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-06 08:34:05
合計ジャッジ時間 1,570 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <set>
#include <functional>
#include "assert.h"
using namespace std;



vector<long long> get_fibonacci_sequence(){
	//fibonacci 1,1,2,3,5,...

	vector<long long> f = {1,0,1,1};
	for(int i=f.size(); f.back() < 2000000000LL; i++){
		f.push_back( f[i-1] + f[i-2] );
	}

	return f;
}

/*
fi fi+1 0 | A   x
fj fj+1 0 | B = y
fk fk+1 0 | 0   z
*/

pair<long long, long long> solver(long long x, long long y , vector<long long>& f, int i, int j){
	if(i==0){
		long long A = x;
		if(f[j+1] == 0) return {1LL<<60, 1LL<<60};
		long long B = y - A*f[j];
		if(B%f[j+1] != 0) return {1LL<<60, 1LL<<60};
		B /= f[j+1];
		if(A <= 0 || B <= 0) return {1LL<<60, 1LL<<60};
		return {A,B};
	}	
	if(i==1){
		long long B = x;
		if(f[j] == 0) return {1LL<<60, 1LL<<60};
		long long A = y - B*f[j+1];
		if(A%f[j] != 0) return {1LL<<60, 1LL<<60};
		A /= f[j];
		if(A <= 0 || B <= 0) return {1LL<<60, 1LL<<60};
		return {A,B};
	}

	long long p = f[i] * y - f[j] * x;
	long long q = f[i] * f[j+1] - f[i+1] * f[j];
	if(q == 0) return {1LL<<60, 1LL<<60};
	if(p%q != 0) return {1LL<<60, 1LL<<60};

	long long B = p/q;
	if(B <= 0) return {1LL<<60, 1LL<<60};


	long long s = x - f[i+1] * B;
	if(f[i] == 0) return {1LL<<60, 1LL<<60};
	if(s%f[i] != 0) return {1LL<<60, 1LL<<60};

	long long A = s/f[i];
	if(A <= 0) return {1LL<<60, 1LL<<60};

	return {A,B};
}


int main(){
	vector<long long> f = get_fibonacci_sequence();

	long long x,y,z;
	cin >> x >> y >> z;

	pair<long long, long long> ans = {1LL<<60, 1LL<<60};

	if(x==y && y==z){
		for(int i=0; i<f.size()-1; i++){
			pair<long long,long long> p;
			p.first = 1;

			long long s = x-f[i];
			if(f[i+1] == 0) continue;

			if(s%f[i+1] != 0) continue;
			p.second = s/f[i+1];
			if(p.second <= 0) continue;

			//cerr << p.first << " " << p.second << endl;

			for(int k=0; k<f.size()-1; k++){
				for(int k=0; k<f.size()-1; k++){
					if(f[k] * p.first + f[k+1] * p.second != z) continue;
					ans = min(p, ans);
				}
			}
		}

	}else{
		if(x==y){
			swap(x,z);
		}
		for(int i=0; i<f.size()-1; i++){
			for(int j=0; j<f.size()-1; j++){
				auto p = solver(x,y, f, i,j);
				if(p >= pair<long long, long long>{1LL<<60, 1LL<<60}) continue;

				//cerr << p.first << " " << p.second << endl;

				for(int k=0; k<f.size()-1; k++){
					if(f[k] * p.first + f[k+1] * p.second != z) continue;
					ans = min(p, ans);
				}
			}
		}
	}

	if(ans >= pair<long long,long long>{1LL<<60, 1LL<<60}){
		cout << -1 << endl;
	}else{
		cout << ans.first << " " << ans.second << endl;
	}
	return 0;
}
0