結果

問題 No.195 フィボナッチ数列の理解(2)
コンテスト
ユーザー chocorusk
提出日時 2018-12-14 10:06:54
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 1,412 bytes
コンパイル時間 1,020 ms
コンパイル使用メモリ 96,476 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-09-25 04:57:38
合計ジャッジ時間 1,987 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
const ll INF=1e9+7;
ll fib[60];
int c;
P solve(ll x, ll y, int i, int j){
	ll d=-fib[i]*fib[j+1]+fib[j]*fib[i+1];
	ll a=-fib[j+1]*x+fib[i+1]*y, b=fib[j]*x-fib[i]*y;
	if(d<0) a=-a, b=-b, d=-d;
	if(a<=0 || b<=0 || a%d!=0 || b%d!=0) return P(-1, -1);
	else return P(a/d, b/d);
}
int main()
{
	fib[1]=1, fib[2]=0;
	for(int i=3; i<60; i++){
		fib[i]=fib[i-1]+fib[i-2];
		if(fib[i]>1e9){
			c=i;
			break;
		}
	}
	ll x, y, z;
	cin>>x>>y>>z;
	if(x==y && y==z){
		ll a=1, b=x;
		for(int k=3; k<c; k++){
			if(x>fib[k] && (x-fib[k])%fib[k+1]==0){
				b=min(b, (x-fib[k])/fib[k+1]);
			}
		}
		cout<<a<<" "<<b<<endl;
		return 0;
	}
	if(x==y) swap(y, z);
	if(x>y) swap(x, y);
	P ans=P(INF, INF);
	for(int i=1; i<c; i++){
		for(int j=i+1; j<c; j++){
			P p=solve(x, y, i, j);
			if(p.first==-1) continue;
			bool ok=0;
			for(int k=1; k<c; k++){
				if(p.first*fib[k]+p.second*fib[k+1]==z){
					ok=1;
					break;
				}
			}
			if(ok) ans=min(ans, p);
		}
	}
	if(ans.first==INF) cout<<-1<<endl;
	else cout<<ans.first<<" "<<ans.second<<endl;
	return 0;
}
0