結果

問題 No.195 フィボナッチ数列の理解(2)
コンテスト
ユーザー btk
提出日時 2015-04-30 18:59:12
言語 C++11（廃止可能性あり）
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 1,858 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 454 ms
コンパイル使用メモリ 61,144 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-05 17:12:46
合計ジャッジ時間 1,243 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<iostream>
#include<algorithm>
#define LL long long 
const LL MAXN = 1e9;
using namespace std;
#define mp(a,b) make_pair(a,b)
typedef pair<LL, LL> P;


inline P calc(LL l1, LL r1, LL l2, LL r2, LL c1, LL c2){
	LL y;
	//if (l1 != 2||l2!=5)return mp(-1,0);
	if (l1 == 0){
		if (r1 == 0 || c1%r1)return mp(-1, 0);
		y = c1 / r1;
	}
	else if (l2 == 0){
		if (r2 == 0 || c2%r2)return mp(-1, 0);
		y = c2 / r2;
		swap(c2, c1); swap(l1, l2),swap(r2,r1);
	}
	else{
		r1 *= l2, c1 *= l2;
		l2 *= l1, r2 *= l1, c2 *= l1;
		r1 -= r2, c1 -= c2;
		if (r1 < 0)r1 *= -1, c1 *= -1;
		if (c1 <= 0 || r1 <= 0 || c1%r1)return mp(-1, 0);
		y = c1 / r1;
	}
	c2 -= r2*y;
	
//	cout << y << " " << c2 << " " << l2 << endl;
	if (c2 <= 0 ||l2<=0 || c2%l2)return mp(-1, 0);
	return mp(c2 / l2, y);
}


int main(){
	LL x, y, z;
	LL left[50] = { 1, 0 };
	LL right[50] = { 0, 1 };
	LL test[50] = { 1, 1 };
	LL sz = 0;
	cin >> x >> y >> z;

	for (int i = 2; left[i - 1] <= MAXN; i++){
		left[i] = left[i - 1] + left[i - 2];
		right[i] = right[i - 1] + right[i - 2];
		test[i] = test[i - 1] + test[i - 2];
//		cout << left[i] + right[i] << " " << test[i] << endl;
		sz++;
	}
	P res = mp(-1ll, 0ll);

	if (x == y&&y == z){
		res = mp(1, x);
		for (int i = 2; i < sz; i++){
			if (x - left[i]>0 && (x - left[i]) % right[i] == 0)
				res = min(res, mp(1ll, (x - left[i]) / right[i]));
		//	cout << right[i] << endl;
		}
	}
	else{
		if (x == y)
			swap(y, z);
		for (int i = 0; i < sz; i++)
			for (int j = 0; j < sz;j++)
				if (i != j){
					auto p = calc(left[i], right[i], left[j], right[j], x, y);
					if (p.first < 0)continue;
					for (int k = 0; k < sz; k++)
						if (z == p.first*left[k] + p.second * right[k])
							if (res.first < 0 || p < res)
								res = p;
				}


	}
	if (res.first>0)
	cout << res.first<<" "<<res.second << endl;
	else cout << -1<<endl;
	return 0;
}
0