C++で最初のN個の自然数の2乗の和がX以下となる最大のNを求める方法

概要

整数 X が与えられたとき、最初の N 個の自然数の2乗の和が X を超えないような最大の N を求めるのが本記事の目的です。

入力例と出力例

例1

X = 7

出力:

2

N = 3 の場合、級数の和は 1² + 2² + 3² = 1 + 4 + 9 = 14 となり X を超えてしまうため、2 が N の最大値となります。

例2

X = 27

出力:

3

N = 4 の場合、1² + 2² + 3² + 4² = 1 + 4 + 9 + 16 = 30 となり X を超えるため、3 が最大値となります。

解法アプローチ

単純な解法(線形探索)

最もシンプルな方法は、1 から順にループを実行し、S(N) ≤ X を満たす最大の N を見つけることです。ここで S(N) は最初の N 個の自然数の2乗の和を表し、次の公式で求められます。

S(N) = N × (N + 1) × (2N + 1) / 6

ただし、この手法の時間計算量は O(N) であり、X が大きくなると非効率になる点に注意が必要です。

効率的な解法(二分探索)

S(N) は N に対して単調増加するため、二分探索を用いることでより効率的に問題を解くことができます。手順は以下の通りです。

• 探索範囲 [low, high] の中央値 mid を (low + high) / 2 として計算する

• squareSum(mid) ≤ X が成り立つ場合、mid は条件を満たす候補となるため答えを更新し、low を mid + 1 に設定してさらに大きい N を探索する

• そうでない場合、mid では和が X を超えるため、high を mid − 1 に設定して小さい側の範囲を探索する

この手法の時間計算量は O(log N) であり、非常に高速に動作します。

C++実装例

// C++による実装例
#include <bits/stdc++.h>
using namespace std;
#define ll long long
// 最初の N1 個の自然数の2乗の和を返す関数
ll squareSum(ll N1){
   ll sum1 = (ll)(N1 * (N1 + 1) * (2 * N1 + 1)) / 6;
   return sum1;
}
// 最初の N 個の自然数の2乗の和が
// X を超えないような最大の N を返す関数
ll findMaxN(ll X){
   ll low1 = 1, high1 = 100000;
   int N1 = 0;
   while (low1 <= high1) {
      ll mid1 = (high1 + low1) / 2;
      if (squareSum(mid1) <= X) {
         N1 = mid1;
         low1 = mid1 + 1;
      }
      else
         high1 = mid1 - 1;
   }
   return N1;
}
// ドライバーコード
int main(){
   ll X = 27;
   cout << findMaxN(X);
   return 0;
}

出力

3