को कम करना पूर्णांक भिन्न एल्गोरिथ्म

Question

(यह एक हाल ही में पूरा प्रोग्रामिंग प्रतियोगिता से ली गई है)

आप रेंज 1..10^7 समावेशी में 10^5 ints के दो सरणियों दिए गए हैं:

int N[100000] = { ... } 
int D[100000] = { ... } 

कल्पना करें कि तर्कसंगत संख्या एक्स एन के सभी तत्वों को एक साथ गुणा करने और डी

एक्स के मान को बदलने के बिना दो सरणी संशोधित करें (और किसी भी तत्व को सीमा से बाहर किए बिना) कि एन के उत्पाद और डी के उत्पाद में कोई कमो नहीं है एन कारक

एक अनुभवहीन समाधान (मुझे लगता है कि) होगा काम करेगा ...

for (int i = 0; i < 100000; i++) 
    for (int j = 0; j < 100000; j++) 
    { 
     int k = gcd(N[i], D[j]); // euclids algorithm 

     N[i] /= k; 
     D[j] /= k; 
    } 

... लेकिन यह बहुत धीमी है।

एक समाधान क्या है जो लगभग 10^9 संचालन से कम लेता है?

Answer 1

गुणनखंड सभी नंबरों को बनाए रखें सीमा 1 से 10 में। एरेटोस्टेनेस की एक चलनी के एक संशोधन का उपयोग करके, आप O(n*log n) समय में सभी संख्याओं को 1 से n में कारक बना सकते हैं (मुझे लगता है कि यह थोड़ा बेहतर है, O(n*(log log n)²) या तो) O(n*log log n) स्थान का उपयोग कर। उससे बेहतर शायद सबसे छोटे प्राइम कारकों की एक सरणी बना रहा है।

// Not very optimised, one could easily leave out the even numbers, or also the multiples of 3 
// to reduce space usage and computation time 
int *spf_sieve = malloc((limit+1)*sizeof *spf_sieve); 
int root = (int)sqrt(limit); 
for(i = 1; i <= limit; ++i) { 
    spf_sieve[i] = i; 
} 
for(i = 4; i <= limit; i += 2) { 
    spf_sieve[i] = 2; 
} 
for(i = 3; i <= root; i += 2) { 
    if(spf_sieve[i] == i) { 
     for(j = i*i, step = 2*i; j <= limit; j += step) { 
      if (spf_sieve[j] == j) { 
       spf_sieve[j] = i; 
      } 
     } 
    } 
} 

एक नंबर n > 1 गुणनखंडों करने के लिए कि चलनी का उपयोग कर, अपनी छोटी से छोटी प्रधानमंत्री कारक p देखो, (n का गुणनखंड में इसकी बहुलता का निर्धारण या तो रिकर्सिवली ऊपर देखकर भी, या बस p जब तक समान रूप से विभाजित करके विभाजित नहीं होता शेष कॉफ़ैक्टर, जो तेजी से निर्भर करता है) और कॉफ़ैक्टर। जबकि कॉफ़ैक्टर 1 से बड़ा है, तो अगले प्रमुख कारक को देखें और दोहराएं।

, N में पूर्णांकों

जाएं अभाज्य संख्या से नक्शा बनाएं दोनों सरणियों के माध्यम से, प्रत्येक संख्या के लिए प्रत्येक प्रधानमंत्री के प्रतिपादक D में नक्शे में मूल्य के लिए अपनी गुणनखंड में जोड़ने के लिए, संख्या के लिए, घटाना।

मानचित्र के माध्यम से जाओ, अगर प्रधानमंत्री के प्रतिपादक सकारात्मक है, सरणी N को p^exponent दर्ज करें (आप छोटे मूल्यों के लिए, में कई अभाज्य संख्या गठबंधन विभाजित करने के लिए है कि कई सूचकांकों भर में अगर प्रतिपादक बहुत बड़ी है की आवश्यकता हो सकती है, और एक प्रविष्टि - 664579 प्राइम्स 10 से कम हैं, इसलिए एक्सोन में 100,000 स्लॉट प्रत्येक उपस्थिति वाले प्राइम को सही शक्ति के साथ स्टोर करने के लिए पर्याप्त नहीं हो सकते हैं), यदि एक्सपोनेंट ऋणात्मक है, तो D सरणी के साथ ऐसा ही करें, यदि यह 0 है, तो उस प्राइम को अनदेखा करें।

N या D में किसी भी अप्रयुक्त स्लॉट को 1 पर सेट किया गया है।

Answer 2

एन & डी में प्रधानमंत्री खंड करना हर तत्व की सुविधा देता है हे में (sqrt (10^7) * 10^5) के रूप में

N[i]=p1^kn1 * p2^kn2 ... 
D[i]=p1^kd1 * p2^kd2 ... 

2 पावर सरणियों जहां

Power_N[p1]=sum of kn1 for all i's 
Power_D[p1]=sum of kd1 for all i's 

Divide the N and D by p1^(min(Power_N[p1],Power_D[p2])) in O(10^5) each 

Answer 3

किसी भी सरणी, क्रमबद्ध, रद्द करने के प्रत्येक तत्व को फैक्टरोरिज़ करें। फैक्टरोरिज्ड बाध्य आकार के इंट्स के लिए निरंतर समय है, सॉर्टिंग एन लॉग एन है, और रद्दीकरण रैखिक होगा। हालांकि, स्थिर कारक बड़े हो सकते हैं।

यदि आप निचले एसिम्प्टोटिक जटिलता के बजाय कम वास्तविक निष्पादन समय की कोशिश कर रहे हैं, तो शायद यह 2, 3, 5, और 7 की शक्तियों जैसे मैन्युअल रूप से छोटे कारकों को रद्द करके सरणी को पूर्ववर्ती करने के लिए चोट नहीं पहुंचाएगा। उच्च संभावना (यानी पैथोलॉजिकल इनपुट को छोड़कर), यह कुछ रैखिक-समय के पास की लागत पर, अधिकांश एल्गोरिदम को तेज कर देगा।

उपर्युक्त दृष्टिकोण को एकीकृत करने वाला एक और परिष्कृत विधि, sqrt(10^7) ~= 3162 तक प्राइम्स की एक सूची बनाकर शुरू करना होगा। प्राइम नंबर प्रमेय द्वारा लगभग 3162/ln(3162) ~= 392 ऐसे प्राइम होना चाहिए। (वास्तव में, चलने वाले समय को बचाने के लिए, आप इस तालिका को प्रीकंप्यूट कर सकते हैं।)

फिर, N में प्रत्येक ऐसे पूर्णांक के लिए, और प्रत्येक प्राइम के लिए, उस प्राइम द्वारा पूर्णांक को कम करें जब तक कि यह समान रूप से विभाजित न हो जाए, और हर बार उस प्राइम के लिए गिनती बढ़ जाती है। D के लिए वही करें, इसके बदले में कमी। एक बार जब आप प्राइम की मेज से गुजर चुके हैं, तो वर्तमान int गैर-1 होगा और केवल तभी होगा जब यह 3162 से बड़ा हो। यह प्रत्येक सरणी में कुल पूर्णांक का लगभग 7% होना चाहिए। आप इन्हें एक ढेर या somesuch में रख सकते हैं। जैसे ही आप साथ जाते हैं, उन्हें सरणी में भी सेट करें।

अंत में, आप सकारात्मक कारकों से अधिक सक्रिय हो जाते हैं और अपने उत्पाद को एन में डाल देते हैं। आपको शायद इसे एकाधिक सरणी स्लॉट में विभाजित करने की आवश्यकता होगी, जो ठीक है। ऋणात्मक कारकों को डी में रखें, और आप कर चुके हैं!

इस पर रनटाइम मुझे काम करने में एक मिनट लगेगा। उम्मीद है कि यह उचित है।

Answer 4

लगभग सब कुछ लिखा गया है, मैं सुझाव है कि देना पी =
जाने q = (डी के सभी तत्वों के गुणन) (एन के सभी तत्वों के गुणन)
एक्स = (p/q); हमेशा स्थिर होना चाहिए
पी, क्यू के प्रमुख कारक खोजें;
संभवतः एक मैट्रिक्स में एक [0] (2 की शक्ति), एक [1] (3 की शक्ति), एक [2] (5 की शक्ति) और इतने पर। अब आप मैट्रिक्स में मानों की तुलना कर सकते हैं और निचले स्तर की शून्य को शून्य में कम कर सकते हैं।
उदाहरण के लिए। पी = 1280 क्यू = 720
पी के लिए [0] = 8 (2 की शक्ति) एक [1] = 0 (3 की शक्ति) एक [2] = 1 (5 की शक्ति); क्यू बी [0] = 4 बी [1] = 2 बी [2] = 1 के लिए
;

एक/दोनों बनाना (के मामले में दोनों कर रहे हैं बराबर) मूल्य/एस शून्य सूचकांक 0,1,2 के लिए .......