由于通过 n \gets n-a,m \gets m-b 和 n \gets n-b,m \gets m-a 两种方式均可兑换奖品，所以 n,m 的顺序显然是可以互换的。
暴力
显然，我们可以写出时间复杂度为 O(n) 的暴力。
大致逻辑为：每次从两种券中选择数量较多的一种，花费较多的这种券来兑换奖品。
代码如下：
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int P=1e9+7;
const int N=1e5+10;
int n,m,a,b,ans;
signed main()
{
cin>>n>>m;
cin>>a>>b;
if(a<b)swap(a,b); //确保 a 较大
while(n>=a||m>=a)
{
if(n<m)swap(n,m);
if(m<b)break;
n-=a;
m-=b;
ans++; //从n,m中选择较大的变量减去较大的花费
}
cout<<ans<<endl;
return 0;
}
正解
注：下文中默认 a \ge b,n \ge m
由于每次我们都让较大的变量减少的更多，所以在进行0次或多次兑换后，$n,m$ 两变量的差值一定会使下次操作后 $n < m$。
具体地，令 $d=a-b,v= \min(n\div a,m\div b,(n-m)\div d)$，则在进行 $v$ 次兑换后，一定会有 $n-m<d$ 或不可再进行兑换。
当 $n-m < d$ 时，下次操作一定会使 $n < m$ 且 $m-n < d$，于是再下次操作又会使 $n > m$，以此类推。
并且在进行两次操作后，由于 $n,m$ 均减去了 $a+b$，操作后的 $n-m$ 与开始的 $n-m$ 大小相等。
因此，当 $n-m < d$ 时，可以令 $y=m \div (a+b)$，进行 $y \times 2 $ 次操作，具体看代码。
### 代码
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int P=1e9+7;
const int N=1e5+10;
int n,m,a,b,ans;
int s,d;
signed main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin>>n>>m;
cin>>a>>b;
if(a<b)swap(a,b);
if(a==b) //进行特判
{
cout<<min(n,m)/a<<endl;
return 0;
}
s=a+b,d=a-b;
while(n>=a||m>=a)
{
if(n<m)swap(n,m);
int x=(n-m)/d;
if(x==0) //当n-m<d时
{
int y=m/s;
ans+=y*2;
n-=y*s,m-=y*s;
x=2;
}
int v=min(n/a,min(m/b,x));
ans+=v,n-=v*a,m-=v*b;
if(m<b)break; //不可进行兑换
}
cout<<ans<<endl;
return 0;
}
```
可以证明，while 循环最多执行**两次**（最开始执行一次使 $n-m<d$，第二次就可兑换完）。
因此，此代码时间复杂度近似 $O(1)