結果
問題 | 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 |
ソースコード
#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; }