3534 - 京城首少
话说，清朝年间。京城中有两个出手阔绰的公子哥，小福王爷和小侯王爷，分别是福王爷和侯王爷的独子。他们闲来无事就喜欢——赌。
这不，小侯王爷这天来到小福王爷府上饮酒。酒过三巡，又离不开赌啦。
小福王爷给小侯王爷出了个难题：
我这有2个宝箱，分别装有黄金若干两。我非常喜欢搜刮民脂，故可以每天往一个宝箱中装入另一个宝箱现在有的黄金数。
具体来说，假设昨日宝箱中分别装有黄金x两和y两，我今天可以往第一个宝箱装y两黄金，或者往第二个宝箱装x两黄金。也就是今天宝箱中的黄金数量可以是(x+y,y)或者(x,x+y)。
现在我有4个宝箱，宝箱中的黄金数分别是a，b,c和d。
你要给我找出一对数x和y，往2个空的宝箱中分别塞入x两黄金和y两黄金。你每天也像我一样这么玩，这宝箱中的黄金数量日后可以变为(a,b)，也可以变为(c,d)。
你若是能找到x和y，我便给你x+y两黄金。你若是能找到多对x和y，我便给你x+y和最大的黄金数。
你若是找不到，这京城首少的名号可是我的了。
你能帮助小侯王爷完成这个难题吗？
以上问题的人话版：
对于数对(x,y)，我们每次可以使之变为(x+y,y)或者(x,x+y)。现在给定4个数字a,b,c和d，请找出数对(x,y)，使得(x,y)经过操作可以变为(a,b)或者(c,d)。变为(a,b)的操作次数可以与变为(c,d)的操作次数不同。
输出x+y的值。如果有多组(x,y)满足条件，输出x+y的最大值。
Input
多组输入数据，每组输入数据包含4个整数a,b,c和d。(1<=a,b,c,d<=1000000)。
Output
对于每组输入数据，输出最大的x+y的值，如果找不到数对(x,y)，输出-1。
Examples
Input
1 2 2 1 15 4 10 7
Output
2 7
Solution C++
#include <iostream> #include <vector> #include <algorithm> #include <string> #include <sstream> #include <cstring> #include <cstdio> #include <cstdlib> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #include <numeric> #include <cassert> #include <complex> #include <ctime> #define clr(x,a) memset(x,a,sizeof(x)) #define sz(x) (int)x.size() #define rep(i,n) for(int i=0;i<n;i++) #define repeat(i, a, b) for(int i=(a);i<=(b);i++) #define all(v) (v).begin(), (v).end() #define Unique(store) store.resize(unique(store.begin(),store.end())-store.begin()) #define X first #define Y second using namespace std; int solve(int a,int b,int c,int d) { set< pair<int,int> >se; se.insert(make_pair(a,b)); while (a!=b) { if (b>a) b-=a; else a-=b; se.insert(make_pair(a,b)); } se.insert(make_pair(a,b)); while (c!=d) { pair<int,int>cur=make_pair(c,d); if (se.count(cur)) return c+d; if (d>c) d-=c; else c-=d; } pair<int,int>cur=make_pair(c,d); if (se.count(cur)) return c+d; return -1; } int main () { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int a,b,c,d; while (scanf("%d %d %d %d",&a,&b,&c,&d)!=EOF) { //assert(a<=1e5&&b<=1e5&&c<=1e5&&d<=1e5); //cout<<"go "<<a<<" "<<b<<" "<<c<<" "<<d<<endl; printf("%d\n",solve(a,b,c,d)); } return 0; }