結果

問題 No.195 フィボナッチ数列の理解(2)
コンテスト
ユーザー hashiryo
提出日時 2019-04-10 20:42:40
言語 C++11（廃止可能性あり）
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 1,752 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 662 ms
コンパイル使用メモリ 95,972 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-08 00:46:22
合計ジャッジ時間 1,366 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 22
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘void init()’:
main.cpp:41:15: warning: iteration 48 invokes undefined behavior [-Waggressive-loop-optimizations]
   41 |       F[i][j] = F[i][j-1]+F[i][j-2];
      |       ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
main.cpp:40:18: note: within this loop
   40 |     for(int j=2;j<=50;j++){
      |                 ~^~~~

ソースコード

diff #
raw source code 

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <limits.h>
#include <math.h>
#include <functional>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <float.h>
#include <random>

#define repeat(i,n) for (int i = 0; (i) < (n); ++ (i))
#define debug(x) cerr << #x << ": " << x << '\n'
#define debugArray(x,n) for(long long hoge = 0; (hoge) < (n); ++ (hoge)) cerr << #x << "[" << hoge << "]: " << x[hoge] << '\n'
#define debugArrayP(x,n) for(long long hoge = 0; (hoge) < (n); ++ (hoge)) cerr << #x << "[" << hoge << "]: " << x[hoge].first<< " " << x[hoge].second << '\n'

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> Pii;
typedef vector<int> vint;
typedef vector<ll> vll;
const long long INF = INT_MAX;
const ll MOD = 1e9+7;

ll F[2][50];
void init(){
  repeat(i,2){
    F[i][0]=!i;
    F[i][1]=i;
    for(int j=2;j<=50;j++){
      F[i][j] = F[i][j-1]+F[i][j-2];
    }
  }
}

int main(){
  init();
  ll X,Y,Z;cin>>X>>Y>>Z;
  ll A=INF,B=INF;
  if(X==Y)swap(Y,Z);
  if(X==Y)X=1;
  for(int p=0;F[0][p]<=X;p++){
    for(int q=0;F[0][q]<=Y;q++){
      ll d=F[0][p]*F[1][q]-F[0][q]*F[1][p];
      ll a=F[1][q]*X-F[1][p]*Y;
      ll b=F[0][p]*Y-F[0][q]*X;
      if(!d||a/d<=0||b/d<=0)continue;
      d = abs(d);
      a = abs(a);
      b = abs(b);
      if(a%d==0&&b%d==0&&(A>(a/d)||((A==a/d)&&(B>b/d)))){
        for(int r=0;F[0][r]<=Z;r++){
          if(a/d*F[0][r]+b/d*F[1][r]==Z){
            A=a/d;
            B=b/d;
          }
        }
      }
    }
  }
  if(A==INF){
    cout<<-1<<endl;
  }else{
    cout << A <<" "<< B <<endl;
  }
  return 0;
}
0