雙正方形：計數數，其是兩個完全平方

源和：Facebook Hacker Cup Qualification Round 2011 雙正方形：計數數，其是兩個完全平方

的雙平方數是一個整數，其X可以被表示爲兩個完全平方的總和。例如，10是一個雙平方，因爲10 = 3 + 1 。給定X，我們如何確定可以寫成兩個平方和的方法的數量？例如，10只能寫成3 + 1 （我們不計數1 + 3 爲不同）。另一方面，25可以寫成5 + 0 或4 + 3 。

你需要解決這個問題0≤X≤2,147,483,647。

實例：

10 => 1
25 => 2
3 => 0
0 => 1
1 => 1

來源

2011-01-11 marcog

只是注意到，這一輪現在已經結束。 – marcog 2011-01-11 11:10:36

沒有像codejam那樣普及。剛剛纔知道這件事。 – 2011-01-11 11:14:45

@Senthil平臺遇到一些問題可能是件好事。 – marcog 2011-01-11 11:15:37

因子數n，並檢查是否有具有奇數估值的素數因子p，例如p = 3（mod 4）。當且僅當n不是兩個平方的總和時纔會這樣做。

解決方案的數量有一個閉式表達式，涉及n的除數。請參閱this, Theorem 3以獲得準確的說明。

來源

2011-01-11 11:47:58

通過對所有對（a，b）進行循環是不可行的，因爲在X上存在約束條件。雖然有更快的方法！

對於固定的a，我們可以計算出b：b =√（X-a ）。 b不會總是一個整數，所以我們必須檢查這個。由於精度問題，請使用一個小容差進行檢查：如果b是x.99999，我們可以相當肯定它是一個整數。因此，我們循環遍歷a的所有可能值並計算其中b是整數的所有情況。我們需要小心不要重複計算，所以我們把約束條件放在< = b。對於X = a + b ，在這個約束條件下，a最多爲√（X/2）。

下面是這個算法的C++實現：

int count = 0; 
// add EPS to avoid flooring x.99999 to x 
for (int a = 0; a <= sqrt(X/2) + EPS; a++) { 
    int b2 = X - a*a; // b^2 
    int b = (int) (sqrt(b2) + EPS); 
    if (abs(b - sqrt(b2)) < EPS) // check b is an integer 
     count++; 
} 
cout << count << endl;

See it on ideone with sample input

來源

2011-01-11 11:09:45 marcog

`對於X = a2 + b2，a和b每個最多√（X/2）`errr ...什麼？這與你在問題中給自己的例子是否直接抵觸？ – fearofawhackplanet 2011-01-11 11:15:17

@fear Err，我會修復的愚蠢的錯誤。 – marcog 2011-01-11 11:17:24

這裏有一個更簡單的解決方案：

create list of squares in the given range (that's 46340 values for the example given) 

for each square value x 
    if list contains a value y such that x + y = target value (i.e. does [target - x] exist in list) 
    output √x, √y as solution (roots can be stored in a std::map lookup created in the first step)

來源

2011-01-11 11:40:36 Skizz

我很匆忙，所以使用Python 2.6的相當蠻力的方法解決了它（非常類似於marcog's）。

def is_perfect_square(x): 
    rt = int(math.sqrt(x)) 
    return rt*rt == x 

def double_sqaures(n): 
    rng = int(math.sqrt(n)) 
    ways = 0 
    for i in xrange(rng+1): 
     if is_perfect_square(n - i*i): 
      ways +=1 
    if ways % 2 == 0: 
     ways = ways // 2 
    else: 
     ways = ways // 2 + 1 
    return ways

注意：ways將是奇數，當數字是一個完美的sqaure。

來源

2011-01-11 12:25:56 dheerosaur

-1

溶液在整數數目的

的x^2 + Y^2 =正

（X，Y）是正好是4次數n全等的約數，以1個模4的數。還存在的問題

類似的身份的x^2 + 2Y^2 =正

和

的x^2 + Y^2 + Z^2 + W^2 = N。

來源

2011-01-11 12:28:40

這是我在O(sqrt(n))複雜簡單的答案

x^2 + y^2 = n 
x^2 = n-y^2 
x = sqrt(n - y^2)

x應是整數所以(n-y^2)應該是完美的正方形。河套y=[0, sqrt(n)]和檢查(n-y^2)是否是完美的方形或不

僞：

count = 0; 
for y in range(0, sqrt(n)) 
    if(isPerfectSquare(n - y^2)) 
     count++ 
return count/2

來源

2011-01-14 05:39:06

這裏有一個版本，這是平凡O（開方（N）），並避免了所有環路內部分支機構。

先開始生成所有方格直到極限，很容易做到沒有任何乘法，然後初始化l和r指數。

在每次迭代中計算總和，然後根據與目標值的比較更新兩個指標和計數。這是sqrt（N）迭代來生成搜索循環的表和最大sqrt（N）迭代。使用合理的編譯器估計運行時間是每sqrt（N）最多10個時鐘週期，因此對於最大輸入值（如果2^31（sqrt（N）〜= 46341），這應該對應於小於500K時鐘週期或幾十分之一秒第二個的：

unsigned countPairs(unsigned n) 
{ 
    unsigned sq = 0, i; 
    unsigned square[65536]; 

    for (i = 0; sq <= n; i++) { 
     square[i] = sq; 
     sq += i+i+1; 
    } 

    unsigned l = 0, r = i-1, count = 0; 

    do { 
     unsigned sum = square[l] + square[r]; 
     l += sum <= n;  // Increment l if the sum is <= N 
     count += sum == n; // Increment the count if a match 
     r -= sum >= n;  // Decrement r if the sum is >= N 
    } while (l <= r); 
    return count; 
}

一個好的編譯器可以注意到，這三個末相比都使用相同的操作數，因此只需要一個單一的CMP操作碼，隨後由三個不同的條件移動操作（CMOVcc指令）。

來源

2016-03-02 13:51:22

雙正方形：計數數，其是兩個完全平方

回答

相關問題