CF317A Perfect Pair 题解

题目传送门

题目大意

给定一对数 \(x\) 和 \(y\)，允许把其中的一个数换成 \(x+y\)，问把 \(x\) 或 \(y\) 变成大于或等于 \(m\) 的数，需要几次操作。

解题思路

• 首先可以判断 \(x\) 或 \(y\) 是否大于 \(m\)，如果是，就是不用进行任何操作就可以比 \(m\) 大，所以可以直接输出 \(0\)；

• 然后在 \(x\) 或 \(y\) 是小于 \(m\) 的情况下再判断 \(x\) 和 \(y\) 是否小于或等于零，如果是，那么 \(x\) 与 \(y\) 的和就永远不可能比 \(x\) 或 \(y\) 大，所以可以直接输出 \(-1\)；

• 如果以上情况都不是，可以判断一下 \(x\) 或 \(y\) 是否有负数，如果有，就一直加 \(y\)，把它变成正数；之后就可以一直让 \(x\) 和 \(y\) 之中小的数加上大的数，直到大于 \(m\) 为止。

代码

#include<bits/stdc++.h>
#define GRET(code) exit(code)
#define ll long long
using namespace std;
ll x,y,m,ans=0;
void maxx(ll x,ll y,ll m){
	if(x>=m||y>=m){
		cout<<0;
		GRET(0);
	}
	else if(x<=0&&y<=0){
		cout<<-1;
		GRET(0);
	}
	else {
		if(x<0){
			ans+=(-x)/y;
			x+=y*((-x)/y);
		} 
		if(y<0){
			ans+=(-y)/x;
			y+=x*((-y)/x);
		}
	}
	while(x<m&&y<m){
		if(x<y) x+=y;
		else y+=x;
		ans++;
	}
}
int main(){
	cin>>x>>y>>m;
	maxx(x,y,m);	
	cout<<ans;
	return 0;
}