BOJ 2731 - 1379와 세제곱

조금 짜증나는 백트랙킹 문제였다. unsigned long long 범위를 벗어나지 않기 위해서는 곱셈과정을 직접 구현해야 한다. 그렇지 않으면 10자리 수에 대한 세제곱 수를 구할 때, 무조건 overflow가 발생한다.

기본 아이디어는 다음과 같다. 일의 자리에 대해서 생각을 해보자. 어떤 한자리 수 세제곱을 하면 숫자 k(0 <= k <= 9)에 대해 표를 만들어보자.

k	1	2	3	4	5	6	7	8	9	0
k*k*k	1	8	7	4	5	6	3	2	9	0

따라서 greedy하게 맨 끝 숫자부터 시작하여 주어진 숫자를 만드면서 답을 만들어가면 된다. 문제 조건에 답은 무조건 있다고 하므로 안심하고 백트랙킹을 시행한다.

미리 10에 대해 제곱수를 계산해두고 이를 modular 연산, 곱셈 연산에 이용하여 시간을 아낀다. 수 0~9까지 하나씩 넣으면서 그 자리 수를 찾고 아니면 돌아와서 계산한다.

#include <cstdio>
using ll = unsigned long long;
int L;
ll ten[15], N, ans;

ll mul(ll a, ll b, ll md) {
	int apos, bpos = 0;
	ll ret = 0, sa, sb;
	while (b / ten[bpos]) {
		sb = b / ten[bpos];
		sb %= 10;
		apos = 0;
		while (bpos + apos <= md) {
			sa = a / ten[apos];
			sa %= 10;
			ret += sb*sa*ten[bpos + apos]%ten[md];
			ret %= ten[md];
			apos++;
		}
		bpos++;
	}
	
	return ret%ten[md];
}

bool back(int p, ll c) {
	if (p == L) {
		ans = c;
		return 1;
	}
	ll t, tt;
	for (ll i = 0; i < 10; i++) {
		tt = c + i*ten[p];
		t = mul(tt, tt, p + 1);
		t %= ten[p + 1];
		t = mul(t, tt, p + 1);
		t %= ten[p + 1];
		if (N%ten[p + 1] != t) continue;
		if (back(p + 1, c + i*ten[p])) return 1;
	}

	return 0;
}
int main() {
	int T;
	ll tmp;
	ten[0] = 1;
	for (int i = 1; i < 15; i++) ten[i] = ten[i - 1] * 10;
	scanf("%d", &T);
	while (T--) {
		ans = 0;
		scanf("%lld", &N);
		tmp = N, L = 0;
		while (tmp) {
			tmp /= 10, L++;
		}
		back(0, 0);
		printf("%lld\n", ans%ten[L]);
	}
	return 0;
}