डबल वर्गों: गिनती संख्या जो दो सही वर्गों

Question

स्रोत की रकम हैं: Facebook Hacker CupQualification Round 2011

एक डबल वर्ग संख्या एक पूर्णांक एक्स जो दो सही वर्गों का योग के रूप में व्यक्त किया जा सकता है। उदाहरण के लिए, 10 एक डबल-स्क्वायर है क्योंकि 10 = 3 + 1 । दिया गया एक्स, हम उन तरीकों की संख्या कैसे निर्धारित कर सकते हैं जिनमें इसे दो वर्गों के योग के रूप में लिखा जा सकता है? उदाहरण के लिए, 10 केवल 3 + 1 के रूप में लिखा जा सकता है (हम अलग होने के रूप में 1 + 3 गिनती नहीं है)। दूसरी तरफ, 25 को 5 + 0 या 4 + 3 के रूप में लिखा जा सकता है।

आपको 0 ≤ एक्स ≤ 2,147,483,647 के लिए इस समस्या को हल करने की आवश्यकता है।

उदाहरण:

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

Answer 1

फैक्टर संख्या n, और देखें कि क्या यह एक है

यहाँ सी में इस एल्गोरिथ्म के ++ एक कार्यान्वयन है अजीब मूल्यांकन के साथ प्राइम फैक्टर पी, जैसे कि पी = 3 (मॉड 4)। यह तब होता है जब केवल एन दो वर्गों का योग न हो।

समाधानों की संख्या में बंद फॉर्म अभिव्यक्ति है जिसमें एन के divisors की संख्या शामिल है। एक सटीक बयान के लिए this, Theorem 3 देखें।

Answer 2

सभी जोड़ों (ए, बी) के माध्यम से लूपिंग एक्स पर बाधाओं को देखते हुए अक्षम है। हालांकि एक तेज तरीका है!

निश्चित के लिए, हम बी: बी = √ (एक्स -) का काम कर सकते हैं। हालांकि हमेशा एक पूर्णांक नहीं होगा, इसलिए हमें यह जांचना होगा। सटीक मुद्दों के कारण, छोटी सहनशीलता के साथ जांच करें: यदि बी x.99999 है, तो हम निश्चित रूप से निश्चित हो सकते हैं कि यह एक पूर्णांक है। तो हम सभी के संभावित मूल्यों के माध्यम से लूप करते हैं और उन सभी मामलों की गिनती करते हैं जहां बी एक पूर्णांक है। हमें सावधान रहने की आवश्यकता है कि डबल-गिनती न करें, इसलिए हम < = b की बाधा डालते हैं। एक्स = + बी , इस बाधा के साथ सबसे अधिक √ (एक्स/2) होगा।

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

Answer 3

यहाँ एक बहुत सरल समाधान है::

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) 

Answer 4

मैं जल्दबाजी में था, इसलिए इसे पाइथन 2.6 का उपयोग करके एक बल्कि ब्रूट-बल दृष्टिकोण (मार्कोग के समान ही) का उपयोग करके हल किया गया।

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 

नोट: नंबर एक आदर्श sqaure है जब ways अजीब हो जाएगा।

Answer 5

समाधान की संख्या पूर्णांक से अधिक

x^2 + y^2 = n

की (एक्स, वाई) वास्तव में 1 आधुनिक 4 n अनुकूल के divisors के 4 गुना संख्या है। इसी प्रकार के पहचान समस्याओं

के लिए भी मौजूद हैं x^2 + 2y^2 = n

और

x^2 + y^2 + z^2 + w^2 = एन।

Answer 6

यहाँ O(sqrt(n)) जटिलता में मेरी सरल उत्तर

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

एक्स होना चाहिए पूर्णांक तो (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 

Answer 7

यहाँ एक संस्करण है जो तुच्छता है ओ (sqrt (एन)) और सभी पाश-आंतरिक शाखाओं से बचा जाता है।

सीमा तक सभी वर्गों को उत्पन्न करके प्रारंभ करें, बिना किसी गुणा के आसानी से किया जाए, फिर एल और आर इंडेक्स शुरू करें।

प्रत्येक पुनरावृत्ति में आप योग की गणना करते हैं, फिर लक्ष्य मान के साथ तुलना में दो सूचकांक और गणना को अपडेट करें। यह खोज लूप के तालिका और अधिकतम वर्ग (एन) पुनरावृत्तियों को उत्पन्न करने के लिए sqrt (एन) पुनरावृत्तियों है। एक उचित कंपाइलर के साथ अनुमानित चलने का समय अधिकतम 10 घड़ी चक्र प्रति वर्ग (एन) है, इसलिए अधिकतम इनपुट मान के लिए यदि 2^31 (वर्ग (एन) ~ = 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; 
} 

एक अच्छा संकलक नोट कर सकते हैं कि तीन अंत में तुलना सभी एक ही ऑपरेंड उपयोग कर रहे हैं तो यह केवल एक ही सीएमपी opcode तीन अलग अलग सशर्त कदम परिचालन (CMOVcc) के बाद की जरूरत है।