CF317A（16th）
hanyuchen2019
·
·
题解
一道简单模拟题，不过有亿点点坑。
part 0
如果你 WA on #10：
### part 1
思路已经很明显了，如果 $x\le y$，就把 $(x,y)$ 改变成 $(x+y,y)$。
一些特殊情况：
1. 如果什么事都没干就已经符合要求了，不考虑任何事，直接输出 $0$。
2. 如果 $x,y$ 皆为负数，且比 $m$ 要小，无论怎么加也无济于事，直接输出 $-1$ 。
### part 2
根据以上所述，我们可以~~快乐的~~写出代码：
```cpp
（头文件，初始化等略）
int main()
{
cin>>x>>y>>m;
if(x>=m||y>=m)//特判1
cout<<0;
else if(x<=0&&y<=0)//特判2
cout<<-1;
else
{
while(x<m&&y<m)
{
if(x>y)swap(x,y);//保持a比b小
x+=y;
ans++;
}
cout<<ans;
}
return 0;
}
```
[结果……](https://www.luogu.com.cn/record/50442227)光荣TLE。
我们来看看TLE的数据：
```
#10 Input:
-1000000000000000000 1 1000000000000000000
```
如果按照此方法，程序要执行 $10^{18}+87$ 次，~~不TLE才怪。~~
### part 3 改进
分析一下这组TLE数据，会发现把 $x$ 变成正数花费了大量时间（一直在把 $x+1$），因为在此过程中一直在做同样的事情，所以我们可以再加上一个优化（在 part 4 中已详细说明）。
### prat 4 AC代码
```cpp
#include<iostream>
#include<algroithm>
using namespace std;
int main()
{
long long x,y,m,ans=0;
cin>>x>>y>>m;
if(x>=m||y>=m)
cout<<0;
else if(x<=0&&y<=0)
cout<<-1;
else
{
if(x*y<0)//如果这两个数一正一负
{
if(x<y)//哪个是负数？
{
ans+=(-x)/y;//这个数要加几次
x=x%y;//等价于 x+=y*((-x)/y)
}
}
ans+=(-y)/x;
y=y%x;
}
while(x<m&&y<m)
{
if(x>y)swap(x,y);
x+=y;
ans++;
}
cout<<ans;
return 0;
}
```
感谢您的观看，点个赞再走吧，bye~