結果

問題 No.3162 Five Two Three
ユーザー hirakich1000000007
提出日時 2025-05-23 19:52:57
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 288 ms / 1,523 ms
コード長 4,279 bytes
コンパイル時間 9,276 ms
コンパイル使用メモリ 220,148 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-05-23 19:54:01
合計ジャッジ時間 60,274 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 187
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
typedef pair<__int128_t, __int128_t> P128;

const ll len = 65;

vector<__int128_t> ans;

template<class T1, class T2>
pair<T1, T2> operator+ (const pair<T1, T2> &l, const pair<T1, T2> &r) {
	return {l.first + r.first, l.second + r.second};
}
template<class T1, class T2>
pair<T1, T2> operator- (const pair<T1, T2> &l, const pair<T1, T2> &r) {
	return {l.first - r.first, l.second - r.second};
}

pair<__int128_t, bool> deduce1 (P128 p, __int128_t a0, __int128_t val) {
	__int128_t war = val - p.first * a0;

	return {war / p.second, (war % p.second == 0)};
}
// pair<__int128_t, bool> deduce1 (__int128_t p, __int128_t val) {
// 	return {val / p, (val % p == 0)};
// }

void seekcand (__int128_t x, __int128_t y, __int128_t z, int xi, int xj) {
	vector<P128> a = {
		{1, 0},
		{0, 1}
	};

	for (int i = 0; i < xi; i++) {
		P128 bl = a[a.size() - 2];
		P128 br = a[a.size() - 1];

		a.push_back(bl - br);
	}
	for (int i = 0; i < xj; i++) {
		P128 bl = a[a.size() - 2];
		P128 br = a[a.size() - 1];

		a.push_back(bl + br);
	}

	// vector<__int128_t> cand;
	for (int zi = 1; zi < a.size(); zi++) {
		for (int yi = zi+1; yi < a.size(); yi++) {
			bool hascand = false;
			__int128_t c = 0;
			if (a[zi].second != 0) {
				auto c_ = deduce1(a[zi], x, z);
				if (!c_.second) continue;
				c = c_.first;
				hascand = true;
			} else if (a[yi].second != 0) {
				auto c_ = deduce1(a[yi], x, y);
				if (!c_.second) continue;
				c = c_.first;
				hascand = true;
			} else {
				// if (x * a[zi].first == z && x * a[yi].first == y) {
				// 	c = 0;
				// 	hascand = false;
				// } else {
				// 	continue;
				// }
				exit(1);
			}

			// cerr << "c ? " << (ll)c << endl;

			if (hascand) {
				if (x * a[zi].first + c * a[zi].second != z) continue;
				if (x * a[yi].first + c * a[yi].second != y) continue;
				bool isgeq0 = true;
				for (int i = 0; i <= yi; i++) {
					__int128_t val = x * a[i].first + c * a[i].second;
					if (val < 0) {
						isgeq0 = false;
						break;
					}
				}
				if (isgeq0) {
					vector<__int128_t> cand;
					for (int i = 0; i <= yi; i++) {
						cand.push_back(x * a[i].first + c * a[i].second);
					}
					if (ans.size() == 0 || cand.size() < ans.size()) {
						ans = cand;
					}

				} else {
					continue;
				}
			} else {
				exit(1);
			}
		}
	}
}

void seek2 (__int128_t x, __int128_t y, __int128_t z) {
	vector<__int128_t> after = {1, 0}, before = {1, 0};
	for (int i = 0; i < len + 5; i++) {
		__int128_t bl = after[after.size() - 2];
		__int128_t br = after[after.size() - 1];
		after.push_back(bl + br);
	}
	for (int i = 0; i < len + 5; i++) {
		__int128_t bl = before[before.size() - 2];
		__int128_t br = before[before.size() - 1];
		before.push_back(bl + br);
	}
	
	vector<__int128_t> a;
	for (int i = before.size() - 1; i >= 0; i--) {
		a.push_back(before[i]);
	}
	for (int i = 0; i < after.size(); i++) {
		a.push_back(after[i]);
	}

	for (int xi = 0; xi < a.size(); xi++) {
		for (int zi = xi+1; zi < a.size(); zi++) {
			for (int yi = zi+1; yi < a.size(); yi++) {
				__int128_t c;
				if (a[xi] != 0) {
					if (x % a[xi] != 0) continue;
					c = x / a[xi];
				} else if (a[zi] != 0) {
					if (z % a[zi] != 0) continue;
					c = z / a[zi];
				} else if (a[yi] != 0) {
					if (y % a[yi] != 0) continue;
					c = y / a[yi];
				} else {
					// because (x, y, z) != (0,0,0)
					continue;
				}

				if (c * a[xi] != x) continue;
				if (c * a[zi] != z) continue;
				if (c * a[yi] != y) continue;
				vector<__int128_t> cand;
				for (int i = xi; i <= yi; i++) {
					cand.push_back(c * a[i]);
				}
				if (ans.size() == 0 || cand.size() < ans.size()) {
					ans = cand;
				}
			}
		}
	}
}

void solve (__int128_t x, __int128_t y, __int128_t z) {
	if (x == 0 && y == 0 && z == 0) {
		ans = {0, 0, 0};
		return;
	}

	for (int i = 0; i < len; i++) {
		for (int j = 0; j < len; j++) {
			seekcand(x, y, z, i, j);
		}
	}

	seek2(x, y, z);
}

int main (void) {
	ll x, y, z;
	cin >> x >> y >> z;

	solve(x, y, z);

	if (ans.size() == 0) {
		cout << "-1\n";
	} else {
		cout << ans.size() << "\n";
		for (int i = 0; i < ans.size(); i++) {
			if (i > 0) cout << " ";
			cout << (ll)ans[i];
		}
		cout << "\n";
	}

	return 0;
}
0