#23643 (C++11) No.195 フィボナッチ数列の理解(2)

• 問題: No.195 フィボナッチ数列の理解(2)
• ユーザー: btk
• 提出日時: 2015-04-30 18:59:12
• 言語: C++11 (gcc 11.4.0)
• 結果: AC
• 実行時間: 2 ms / 5,000 ms
• コード長: 1,858 bytes
• コンパイル時間: 480 ms
• コンパイル使用メモリ: 63,220 KB
• 実行使用メモリ: 4,380 KB
• 最終ジャッジ日時: 2023-09-19 04:41:25
• 合計ジャッジ時間: 1,667 ms
• ジャッジサーバーID （参考情報）: judge15 / judge14

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 4,380 KB
testcase_01	AC	1 ms; 4,380 KB
testcase_02	AC	2 ms; 4,376 KB
testcase_03	AC	2 ms; 4,376 KB
testcase_04	AC	2 ms; 4,380 KB
testcase_05	AC	2 ms; 4,380 KB
testcase_06	AC	2 ms; 4,376 KB
testcase_07	AC	1 ms; 4,376 KB
testcase_08	AC	2 ms; 4,380 KB
testcase_09	AC	2 ms; 4,380 KB
testcase_10	AC	1 ms; 4,380 KB
testcase_11	AC	2 ms; 4,376 KB
testcase_12	AC	2 ms; 4,376 KB
testcase_13	AC	1 ms; 4,376 KB
testcase_14	AC	2 ms; 4,376 KB
testcase_15	AC	2 ms; 4,380 KB
testcase_16	AC	2 ms; 4,380 KB
testcase_17	AC	1 ms; 4,380 KB
testcase_18	AC	1 ms; 4,376 KB
testcase_19	AC	1 ms; 4,376 KB
testcase_20	AC	1 ms; 4,376 KB
testcase_21	AC	1 ms; 4,380 KB
testcase_22	AC	2 ms; 4,376 KB
testcase_23	AC	2 ms; 4,380 KB
testcase_24	AC	2 ms; 4,376 KB

ソースコード

#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;
}