[토요라운드] B. 2의 제곱수 계산하기 (19946)

문제가 너무 어려워 보였음... 64번 곱하기... 게다가 long long 범위도 벗어남.. 그래서 처음에 어떻게 할지 생각하다가 고민 좀 더 하면 풀 수 있을 것 같아서 미뤄두고 나중에 다시 풀었다. 

 

가장 단순하게 생각했다. 0번째에 실수한 경우 1번째.. 64번째에 실수한 경우 전부 저장해두자! 그리고 입력값이랑 비교해서 일치하는 걸 찾는거지. 문제는 longlong보다 큰 수가 나와서 범위를 벗어나는 건데.. 이건 이전에 풀었던 피보나치 수 문제에서 도움을 받았다. 

 

이전에 피보나치 순열 푸는 (잘 기억 안 난다) 문제가 있었는데 이 문제를 해시를 써서 풀었다. 해시 키 값은 마지막 10자리를 기준으로 해서 풀었다. 이 때 실수로 겹치는 수가 있으면 어카지?? 생각했는데 10자리면 겹치는 일 없다고 북님한테 들었던 기억이 났다. 그래서 저장하는 것도 마지막 10자리 수만 저장했다. 입력 받는 것도 문제니깐 문자열로 입력 받고 마지막 10자리만 숫자로 만들었음. 이렇게 솔브~~~

 

이전에 배웠던 거 써먹어서 족금 뿌듯하다

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;


int     main()
{
	string s;
	cin >> s;

	if (s.size() > 10)
		s = s.substr(s.size() - 10);

	i64 n = stoll(s);

	vector<i64> ans(65);
	for (int i = 0; i <= 64; i++)
	{
		i64 x = 1;

		if (i == 0)
			x--;

		for (int j = 1; j <= 64; j++)
		{
			x = (x * 2) % 10000000000;
			if (i == j)
				x--;
		}

		ans[i] = x;
	}

	for (int i = 0; i < ans.size(); i++)
	{
		if (n == ans[i])
			printf("%d\n", i);
	}

	return 0;
}