백준17167 A Plus Equals B

작성일 | In

문제 링크

  • http://icpc.me/17167

문제 출처

  • 2019 KAIST RUN Spring Contest D번

풀이

a += a는 b /= 2와, b += b는 a /= 2와 같은 역할을 하기 때문에, a += a와 b += b를 b /= 2와 a /= 2로 바꿔서 쓸 수 있습니다.
큰 숫자를 다루기 싫으므로, A 혹은 B가 짝수라면 열심히 2로 나누어줍시다.

a와 b가 홀수이고, a > b인 경우를 생각해봅시다.(a < b인 경우에도 똑같이 처리할 수 있습니다.)
a += b, a /= 2(a += b, b += b)를 해주면 |a - b|의 값이 절반으로 감소하게 됩니다.
그러므로 log |a - b|번만 이 연산을 해주면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

string s[5] = {
	"",
	"A+=A",
	"A+=B",
	"B+=A",
	"B+=B"
};

int main(){
	ll a, b; cin >> a >> b;
	int cnt = 0;
	vector<int> v;
	if(a == b){
		cout << 0; return 0;
	}

	while(~a & 1){
		cnt++; a >>= 1LL; v.push_back(4);
	}
	while(~b & 1){
		cnt++; b >>= 1LL; v.push_back(1);
	}
	while(a ^ b){
		if(a > b){
			a += b; cnt++; v.push_back(2);
		}else{
			b += a; cnt++; v.push_back(3);
		}
		while(~a & 1){
			cnt++; a >>= 1LL; v.push_back(4);
		}
		while(~b & 1){
			cnt++; b >>= 1LL; v.push_back(1);
		}
	}
	cout << cnt << "\n";
	for(auto i : v) cout << s[i] << "\n";
}