题解：P15632 [2019 KAIST RUN Spring] A Plus Equals B

· · 题解

思路

这道题我们可以发现操作里的 a \leftarrow 2a 和 b \leftarrow 2b 可以改变 a 或 b 的奇偶性，但只能变为偶数，那么如果 a 为偶数， b 为奇数时，我们就让 b \leftarrow 2b ，这个操作等价于 a \leftarrow \frac{a}{2} ，如果 b 为偶数， a 为奇数时，我们就让 a \leftarrow 2a ，这个操作等价于 b \leftarrow \frac{b}{2} ，然后我们再让大的加上小的，一直循环到 a = b 即可。

证明

因为每次 a 和 b 都要一直除 2 ，所以最多执行 \log_2 {{10}^{18}} \approx 60 轮，可能要多一点，那么我们假设进行了 70 轮，那么每轮都要进行除和加，那么每轮最多执行 60 + 1 = 61 次，那么操作数最多为 70 \times 61 = 4260 ，小于 5000 。

代码

#include<bits/stdc++.h>
#define PII pair<int,int>
#define int long long
using namespace std;
const int MAXN=1e6+5;
int a,b,op[MAXN],cnt;
string s[]={"A+=A","A+=B","B+=A","B+=B"};
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    cin>>a>>b;
    while(a!=b){
        while(a%2==0)a/=2,op[++cnt]=4;
        while(b%2==0)b/=2,op[++cnt]=1;
        if(a>b)a+=b,op[++cnt]=2;
        else if(a<b)b+=a,op[++cnt]=3;
    }cout<<cnt<<'\n';
    for(int i=1;i<=cnt;i++)cout<<s[op[i]-1]<<'\n';
    return 0;
}