E: Forever Young
問題
私はY歳です。
適切なBを求めて、「YをB進数で表した時全ての桁は0~9であり、その表示を十進数とみなすとL以上である」ようにしなさい。
その最大のBを出力しなさい。
制約
10 <= Y <= 10^18
10 <= L <= Y
解法
Bを1つ選んでYのB進数表示を求めるのは簡単。しかし現実的な時間では精々B <= 10^6 ~ 10^7 程度までである。
Bが10^6より大きい時にそのB進数表示は3桁以下である。なぜなら4桁目が1以上ならば元の数がB^3以上でありYの上限を超えるから。
よって平方分割(立法分割?)が適している。
3桁の表示が全て0~9の場合を決めて、逆にBを方程式を解くなり、二分探索を行うなり求める。
コード
汚い。チーム戦なら解を洗練してからコーディングするべき。
#include<cstdio> #include<iostream> #include<vector> #include<algorithm> #include<string> #include<cstring> using namespace std; typedef long long LL; typedef vector<int> VI; #define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i) #define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i) #define eprintf(s...) fprintf(stderr, s) template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; } template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; } LL Y, L; int main() { scanf("%lld%lld", &Y, &L); LL ans = 10; for (LL b = 11; b <= 1000000; b++) { LL yy = Y; LL d = 0, t = 1; bool ok = true; while (yy) { if (yy % b >= 10) { ok = false; break; } d += (yy % b) * t; t *= 10; yy /= b; } if (ok && d >= L) { amax(ans, b); } } REP (a0, 10) REP (a1, 10) REP (a2, 10) REP (a3, 10) { if (a3 * 1000 + a2 * 100 + a1 * 10 + a0 < L) continue; LL lo = 10, hi = 2e18 + 10; while (hi - lo > 1) { LL m = (hi + lo) >> 1; double d = m; if (a3 * d * d * d + a2 * d * d + a1 * d + a0 > 2e18) hi = m; else if (a3 * m * m * m + a2 * m * m + a1 * m + a0 > Y) hi = m; else lo = m; } LL m = lo; if (a3 * m * m * m + a2 * m * m + a1 * m + a0 == Y) { amax(ans, m); } } printf("%lld\n", ans); return 0; }