Prime Square Sum

コンテスト中

• とりあえず素数列挙。これは$O(N\sqrt{N})$
• 1000000以下の素数の個数は78498個だった。なので、愚直に３重ループでの実装は無理。
• ２重ループも考えたけどきつそう。行けたとしてもsqrt使わなきゃダメっぽい
• よくわかんなくなって終了

理想の考察

• とりあえず素数列挙する。計算量は$O(N\sqrt{N})$
• 素数の個数は78498個になる。なので、愚直に３重ループとかは無理。計算量減らしたい
• 素数の値が大きい場合、$A^2 + B^2 + C^2 = N$の左辺がめちゃくちゃ大きくなるのに気がつく。この辺で無駄な計算してるのでは？となる
• ここで、$A^2, N$のみに注目してみる。$A^2$と$N$の大きさの関係を考えてみる。$B^2 > 0, C^2 > 0$より、$A^2 < N$である。この式でルートをとると、$A < \sqrt{N}$ となる。よって、列挙する素数は$\sqrt{N}$未満で良さそうだ
• 念の為もう少し考えると$A \geq \sqrt{N}$の場合、両辺を2乗すると$A^2 \geq N$となる。なので、$A^2 \geq N$のとき、$B, C$をどれだけ小さくしようとしても$A^2 + B^2 + C^2 > N$となってしまう。なので、$\sqrt{N}$以上の素数を列挙しても計算に使わないため列挙する意味がないことがわかる

解法

1. $\sqrt{N}$以下の素数を列挙する
2. 列挙した素数で3重ループを回す

コード

#include <bits/stdc++.h>
using namespace std;

#define int long long

vector<int> prime;

void init() {
  prime.push_back(2);
  for (int ni = 3; ni*ni <= 1000000; ni++) {
    bool flg = true;
    for (int j = 2; j*j <= ni; j++) {
      if (ni % j == 0) {
        flg = false;
        break;
      }
    }
    if (flg) {
      prime.push_back(ni);
    }
  }
}

signed main() {
  init();
  int t; cin >> t;
  while (t--) {
    int n; cin >> n;

    int ans = 0;
    for (int i = 0; i < prime.size(); i++) {
      for (int j = i; j < prime.size(); j++) {
        for (int k = j; k < prime.size(); k++) {
          int a = prime[i], b = prime[j], c = prime[k];
          if (a*a + b*b + c*c == n) {
            ans++;
          }
        }
      }
    }
    cout << ans << endl;
  }


  return 0;
}

要点

• 無駄に計算している部分を見つける。