NPCA Judge #59: 17歳だよ?!進数変換祭り!! https://judge.npca.jp/problems/view/59

17sai.cpp

#include <iostream>
#include <algorithm>

int base2dec(int n, int base) {
	int s = 0;
	int place = 1;
	for (int i = n; i >= 1; i /= 10) {
		s += (i % 10) * place;
		place *= base;
	}
	return s;
}

int getMaxNum(int n) {
	int m = 0;
	for (int i = n; i >= 1; i /= 10) {
		m = std::max(m, i % 10);
	}
	return m;
}

int getBase(int real, int imag) {
	int bMin = getMaxNum(imag) + 1, bMax = real;
	while (bMin <= bMax) {
		const int b = (bMin + bMax) / 2;
		const int s = base2dec(imag, b);
		if (s == real) {
			return b;
		} else if (s < real) {
			bMin = b + 1;
		} else {
			bMax = b - 1;
		}
	}
	return -1;
}

int main() {
	for (int real, imag; std::cin >> real >> imag;) {
		if (real == 0 && imag == 0) {
			break;
		}
		const int base = getBase(real, imag);
		if (base >= 0) {
			std::cout << base << std::endl;
		} else {
			std::cout << "NA" << std::endl;
		}
	}
	return 0;
}