小M的操作數

時間限制：1000?ms ?|? 內存限制：65535?KB 難度：2 描述

最近小M上課老瞌睡，落下許多功課，現在就遇到了一個問題： 當一個數對（x，y）中有一個數大于或等于m時（當然有兩個更好了），我們稱它為m數對。一個數對（x，y）可以經過一步操作變成變成（x，x+y）或（x+y，y）數對。現在計算一個數對（x，y）變成m數對最少的操作次數嗎？?你能幫助小M嗎，輸出最小的操作次數，如果不能變成m數對輸出-1。 輸入

輸入x，y，m，( -10^18 ≤ x , y , m ≤?10^18 )

輸出

輸出結果。

樣例輸入

1 2 5 0 -1 5

樣例輸出

2 -1

此題是給定（x，y）數對，問至少經過多少次變換能使至少有一個數大于或等于m。

假設x>0,y>0,我們每次用x+y來替換x,y中較小的那個，假設x<y,則第一次操作后變成（x+y，y），第二次操作后變成（x+y，x+2*y)

第三次后變成（2*x+3*y，x+2*y)…………第k次操作后較大的數等于fib[k]*y + fib[k-1]*x,其中fib[ ]是斐波那契數。

對于x，y小于0的，轉換成正的即可。

#include<stdio.h> #include<algorithm> using namespace std; typedef long long LL; LL fib[100]; void get_fib() {fib[0] = 1; fib[1] = 1;for(int i = 2; i <= 90; i++)fib[i] = fib[i-1] + fib[i-2]; } int main() {get_fib();LL x, y, m;while(~scanf("%lld%lld%lld",&x, &y, &m)){LL temp, i, sum = 0;if(x >= m || y >= m){printf("0\n");continue;}if(x > y) swap(x,y);if(x <= 0 && y <= 0){if(y >= m) printf("0\n");else printf("-1\n");continue;}if(x < 0 && y > 0){sum = (-x) / y + 1;x += sum * y;}//求出把x變成正數需要的次數if(x > y) swap(x,y);for(i = 1; i <= 90; i++){temp = fib[i]*y + fib[i-1]*x;if(temp >= m)break;}printf("%lld\n",sum + i);}return 0; }

總結

以上是生活随笔為你收集整理的NYOJ 875 小M的操作数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。