A. Perfect Pair
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Let us call a pair of integer numbers m-perfect, if at least one number in the pair is greater than or equal to m. Thus, the pairs (3, 3) and (0, 2) are 2-perfect while the pair (-1, 1) is not.
Two integers x, y are written on the blackboard. It is allowed to erase one of them and replace it with the sum of the numbers, (x y).
What is the minimum number of such operations one has to perform in order to make the given pair of integers m-perfect?
Input
Single line of the input contains three integers x, y and m ( - 1018 ≤ x, y, m ≤ 1018).
Please, do not use the %lld specifier to read or write 64-bit integers in C . It is preffered to use the cin, cout streams or the %I64dspecifier.
Output
Print the minimum number of operations or "-1" (without quotes), if it is impossible to transform the given pair to the m-perfect one.
Sample test(s)
input
代码语言：javascript复制1 2 5output
代码语言：javascript复制2input
代码语言：javascript复制-1 4 15output
代码语言：javascript复制4input
代码语言：javascript复制0 -1 5output
代码语言：javascript复制-1题意：
给你x 和 y 还有M，让你通过变换x和y，使得其中一个大于或者等于m，变换的方法就是自身加上另外一个，如果可以通过若干步使满足条件，输出最小的步数，否则输出-1。
思路： 如果xy小于0且m大于0，那么肯定不可能变换到m，如果 x < m && y < m && x y<0也肯定没办法达到m。
我先排除了输出-1的，然后再考虑如何计算最小的步数。我们主要在每一步中最小一个加上另一个就可以了，这是朴素的求法，但可能出现这样的情况 比如 -100000000 1 10000000 这样的话会循环100000000多次，肯定超时，所以我们要加快速度。
代码：
代码语言：javascript复制//cf 317 A
//2013-06-22-16.43
#include <iostream>
using namespace std;
int main()
{
__int64 x, y, m;
while (cin >> x >> y >> m)
{
if (x <= 0 && y <= 0)
{
if (x < m && y < m && x y <= 0)
{
cout << "-1" << endl;
continue;
}
}
__int64 ans = 0;
int cnt = 0;
while (x < m && y < m)
{
if (x > y)
{
__int64 t = x; x = y; y = t;
}
if (x < 0 && y > 0 && -x > y)
{
ans = (-x)/y;
x = (-x)/y * y;
}
else
{
x = x y;
ans ;
}
}
cout << ans << endl;
}
return 0;
}
