algorithm - 整数を 4 つの平方和として表す

Question

正の整数が与えられたとき、 となる4つの整数、、をm見つけます。余分なスペースを使用できます。abcda^2 + b^2 + c^2 + d^2 = mO(m^2 log m)

私は解決策を考えることができますが、O(m^3)解決策について混乱していO(m^2 logm)ます..

Answer 1

すべての自然数は4つの二乗の合計であるというラグランジュの古典的な定理があります。

このトピックに関するウィキペディアのページには、O（\ lg ^ 2 m）時間で実行される表現を計算するためのランダム化アルゴリズムがあると記載されています（上記のすべての提案はmの多項式です。つまり、問題のサイズは指数関数的です。インスタンス（数mは\ lg mビットでエンコードできるため）。

余談ですが、ラグランジュの定理は、プラスと時間の整数の決定不能性を証明します（自然は決定不可能であり、定理のおかげでプラスと時間の整数で定義できるため）。

Answer 2

最初のヒント:

二乗要素を 1 から m^2 に並べ替える複雑さは何ですか?

2 番目のヒント:

ヘルプについては、この投稿をご覧ください。

休憩時間、O(n^2) でピタゴラス方程式に一致するトリプルを見つけます

3 番目のヒント:

さらにヘルプが必要な場合: (前の投稿の yi_H の応答から):

O(n^2 log n) は数値をソートし、任意の 2 つのペア (O(n^2)) を取り、c^2 = a^2 + b^ の数値に c があるかどうかを確認することだと思います2. O(log(n)) である二分探索で c のルックアップを行うことができます。

作者: yi_H

n と sqrt(m) を比較します。

これで解決策を見つけていただければ幸いです。