마이다스 18년 대회 4번

1100 1101

이라는 숫자 (10진수로 들어옴)를

100 이라는 숫자(마찬가지로 10진수로 들어옴)를

패턴으로 때는 문제

예를들어

11001101

은

100으로 때면

1 100 1101 -> 1 1101 -> 11101 

이다

이건 연속적으로 가능 해서

 

1101000100

-> 1 10 100 0 100

-> 1 10 0

-> 1 100

-> 1

이렇게 될 수 있다

그렇게 계산된 결과의 자리수를 구하는 문제

string으로 풀면 될까 싶었는데, 나눗셈과 쉬프트를 이용해서 풀었다.

#define INT_MAX_ 2100000000;

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#include <vector>
#include <string>
#include <utility>
#include <algorithm>
#include <stack>
#include <queue>
#include <functional>

using namespace std;

typedef long long int lld;

lld N, X;

int main() {
	cin >> N;
	cin >> X;

	lld temp, firstNum;
	lld xRadix = 1;
	bool flag = true;
	bool zeroFlag = false;

	for (int i = 0; i < log2(X) + 1; i++) {
		if (xRadix > X) {
			break;
		}
		xRadix *= 2;
	}


	while (flag) {
		//zeroFlag = false;

		int i;
		for (i = 0; i < log2(N); i++) {
			temp = N >> i;
			firstNum = temp - X;
			if (firstNum < 0) break;
			if ((firstNum % xRadix) == 0) {
				flag = false;
				break;
			}
		}
		if (flag) {
			break;
		}

		if (N == X) {
			zeroFlag = true;
		}
		N = ((firstNum >> (int)(log2(xRadix))) << i) + (N % (int)pow(2, i));

		flag = true;
	}

	

	if (N == 0) {
		if (zeroFlag) cout << 0 << endl;
		else cout << 1 << endl;
	}
	else {
		cout << (int)log2(N) + 1 << endl;
	}

	return 0;
}