这里有两个变量,一个是进制,一个是对应进制下的长度。可以固定一个变量,然后判断是否满足条件即可。进制的取值范围为 [2, n - 1],范围太大,所以应该固定长度,判断是否存在满足条件的进制。进制越小,长度越长;进制越大,长度越短。我们可以从大到小枚举长度,判断是否存在满足条件的进制,这一步可以运用二分查找。
classSolution { public: using ll = longlong; ll nextK(ll k, ll m, ll N, bool& match){ match = false; ll lo = k + 1; ll hi = N - 1; while (lo <= hi) { ll md = lo + (hi - lo) / 2; ll s = 0; for (ll i = 0; i <= m; ++i) { if (s > (N - 1) / md) { s = N + 1; break; } s = s * md + 1; } if (s == N) { match = true; return md; } if (s > N) hi = md - 1; else lo = md + 1; } return lo; } ll nextM(ll k, ll m, ll N, bool& match){ match = false; ll lo = 1; ll hi = m - 1; while (lo <= hi) { ll md = lo + (hi - lo) / 2; ll s = 0; for (ll i = 0; i <= md; ++i) { if (s > (N - 1) / k) { s = N + 1; break; } s = s * k + 1; } if (s == N) { match = true; return md; } if (s > N) hi = md - 1; else lo = md + 1; } return hi; } string smallestGoodBase(string n){ ll N = stoll(n); ll k = 2; ll m = N; // m为N表示为k进制的最高次幂 bool match = false; while (k < N && m > 0) { m = nextM(k, m, N, match); if (match) break; k = nextK(k, m, N, match); if (match) break; } returnto_string(k); } };