數論定理Fermat二平方和與Leetcode 633 C++解答打敗100趴
openai-whisper字幕。
#數論 定理#Fermat 二平方和(Sum of Two Squares): p為奇質數，p=a^2+b^2有正數解若且唯若p=1(mod 4)
用此定理的推廣到n的結果來撰寫Leetcode 633 C++解答打敗100趴。此解只是檢驗存在性的充分必要條件，須知當n為合成數時，解非唯一，但n=p為質數時，其解是唯一的(如果要考慮排列、正負數就唯四)，可用高斯18歲就能證明的Quadratic Reciprocity，演算方式可是輾轉相除，又快又準，比上暴力解好上許多，續待中
===
Fermat Sum of Two Squares: p is an odd prime number, p=a^2+b^2 has a positive solution if and only if p=1 (mod 4)
Use the generalization of this theorem to n to write the Leetcode 633 C++ solution and beat 100%. This solution is only an equivalent condition to test the existence. It should be noted that when n is a composite number, the solution is not unique, but when n=p is a prime number, the solution is unique (if you want to consider permutations, positive and negative numbers, it is only four), You can use Quadratic Reciprocity, which Gauss was able to prove when he was 18 years old. The calculation method is Euclidean division, which is fast and accurate. It is much better than the solution by brutal force.
「數論&質數, Prime Numbers, Primzahlen --playlist」 • 篩法找質數、質數定理與C++ STL vector程式實作(Sieve method...