#include #include #include #include #include using namespace std; typedef long long ll; // 異なる平方数の和で作れない数は最大でも128付近であるため、 // 小さい範囲の判定用に定数を用意 const int MAX_IMPOSSIBLE = 150; // k段のピラミッドに必要なブロック総数 // オーバーフローを防ぐため __int128 を使用するか、制限内で計算する ll get_total_blocks(ll k) { // k(k+1)(2k+1)/6 // k <= 2*10^6 なので、計算結果は高々 ~2.6*10^18 程度。long longに収まる。 // 計算途中のオーバーフローに注意 unsigned __int128 K = k; unsigned __int128 total = K * (K + 1) * (2 * K + 1) / 6; if (total > 4000000000000000000ULL) return 4000000000000000000LL; // 飽和 return (ll)total; } // 小さいkに対する厳密なDP判定 // bitsetを使って到達可能な和を列挙する bool check_small(ll k, ll R, ll B) { ll total = get_total_blocks(k); if (total > R + B) return false; // 必要な赤ブロックの数の候補範囲: [max(0, Total - B), min(Total, R)] ll min_r = max(0LL, total - B); ll max_r = min(total, R); if (min_r > max_r) return false; // DPで到達可能な和を計算 // k=20のとき total=2870 なので bitset<3000> で十分 bitset<3000> dp; dp[0] = 1; for (int i = 1; i <= k; ++i) { ll sq = i * i; dp |= (dp << sq); } // 範囲内にtrueがあるか探す // min_r から max_r まで for (ll r = min_r; r <= max_r; ++r) { if (r < 3000 && dp[r]) return true; } return false; } // 判定関数 bool check(ll k, ll R, ll B) { // kが小さい場合はDPで厳密に解く if (k <= 20) { return check_small(k, R, B); } ll total = get_total_blocks(k); if (total > R + B) return false; // kが大きい場合 // 到達不可能な数は小さい値(最大128)に限られることが知られている。 // 範囲 [min_r, max_r] が 128 より大きい値を含んでいれば、必ず到達可能。 // もし範囲全体が 128 以下なら、それは「小さい数」のチェックが必要だが、 // k > 20 で Total は数千になるため、 // R, B が極端に小さくない限り範囲は128を超える。 ll min_r = max(0LL, total - B); ll max_r = min(total, R); if (min_r > max_r) return false; // 範囲の上限が128を超えていれば、129以上の数はすべて作れる(k>20なら十分な1,4,9...があるため) // 正確には「異なる平方数の和で表せない最大整数」は128。 if (max_r > 128) return true; // ここに来るのは R, B の片方が極端に小さく、必要なブロック数が128以下に収まる場合。 // k > 20 で Total > 2000 なのに ターゲットが <= 128 ということは // ほぼすべてのブロックをもう一方の色にする必要がある。 // 小さい数は k=20 までの平方数で作れるかどうかのチェックで十分(1..20の2乗があれば128以下は網羅できる) // 念のため事前に計算しておいた「作れない数リスト」でチェック // 128以下の作れない数: // 2, 3, 6, 7, 8, 11, 12, 15, 18, 19, 22, 23, 24, ... (OEIS A001422) // 毎回DPするのは重くないので、ここでも部分的にDPを回して確認する bitset<150> dp; dp[0] = 1; // 128を作るのに必要なのは高々12^2=144まで。k>20なので十分足りる for (int i = 1; i <= 20; ++i) { int sq = i * i; if (sq > 130) break; dp |= (dp << sq); } for (ll r = min_r; r <= max_r; ++r) { if (dp[r]) return true; } return false; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); ll R, B; if (cin >> R >> B) { ll low = 0, high = 2000000; // 2*10^6 程度が上限 ll ans = 0; while (low <= high) { ll mid = low + (high - low) / 2; if (check(mid, R, B)) { ans = mid; low = mid + 1; } else { high = mid - 1; } } cout << ans << endl; } return 0; }