P8348 「Wdoi-6」未知之花魅知之旅
天南星魔芋
·
·
题解
注意坑点：a0,a1 可能和 x,y 相同并且 a0 或 a1 不大于 k。
思路：
因为让 a0,a1 凑 x,y 肯定不行（1e9），所以考虑将这两对数化作相同的一对数。
然后想到往小凑。（因为往大凑的话没有上界，肯定不行）
若一数对能构成的最小数对的唯一，并且求最小数对方法正确，所以只要求出 a0,a1 构成的最小数对 和 x,y 构成的最小数对，然后比较他俩是否一样就行了。（注意数对中两个数的先后顺序）
然后就是证明一数对能构成的最小数对的唯一，并且方法正确：
-
对于一对数，若只考虑减法，那么只有一种构造方案。
-
加入加法，设当前为 x,y ，加一次后就是 y,y+x，然后对 y,y+x 持续做减法：y,y+x 变成 y+x,x 变成 x,y，也就是我们发现一次加法可以被两次减法抵消，加法对于结果没有影响。
也就是说只要不断做减法，直到无法运算为止，就能得出构成的最小数对。
因为求最小数对方法唯一，所以构成的最小数对唯一。
然后我们模拟减法，即可拿到 50 分。
```cpp
#include<bits/stdc++.h>
using namespace std;
int T;
int x,y,xx,yy,k;
void cl(int &a,int &b){
while(1){
int ABS=abs(a-b);
if(ABS>=k){
a=b;
b=ABS;
}
else break;
}
}
signed main(){
cin>>T;
while(T--){
scanf("%d%d%d%d%d",&x,&y,&xx,&yy,&k);
if(k>xx||k>yy||k>x||k>y){
puts("no");
continue;
}
if(x==xx&&y==yy){
puts("yes");
continue;
}
cl(x,y);cl(xx,yy);
if(xx!=x||yy!=y)puts("no");
else puts("yes");
}
}
```
思考为什么 T 了，发现模拟减法算法复杂度高。（比如一个 1e9 ，一个 1，肯定 T）
然后就是对模拟减法的优化，我们对于连减要分类讨论一下：
* $x,y$ 并且 $x>y$ $x,y$ 变成 $y,x-y$ 变成 $x-y,x-y-y$ 变成 $x-y-y,y$。
* $x,y$ 并且 $x<y$ $x,y$ 变成 $y,y-x$ 变成 $y-x,x$ 变成 $x,y-x-x$。
通过观察发现，若大的超过了小的的两倍，那么大的可以直接减去两个小的并且不做交换。
我们每次可以观察大的可以减去多少个小的，若为奇数个，减完交换，否则就直接减。
$code:$ 100 pts
```cpp
#include<bits/stdc++.h>
using namespace std;
int T;
int x,y,xx,yy,k;
void cl(int &a,int &b){
while(1){
if(a<b){
int now=(b-k)/a;
if(!now)break;
b-=now*a;
if(now&1)swap(b,a);
}
else if(a>b){
int now=(a-k)/b;
if(!now)break;
a-=now*b;
if(now&1)swap(a,b);
}
else break;
}
}
signed main(){
cin>>T;
while(T--){
scanf("%d%d%d%d%d",&x,&y,&xx,&yy,&k);
if(k>xx||k>yy||k>x||k>y){
puts("no");
continue;
}
cl(x,y);cl(xx,yy);
if(xx!=x||yy!=y)puts("no");
else puts("yes");
}
}
```
~~所以这有黑题难度吗？~~