लघुत्तम समापवर्त्य (LCM)
दो संख्याओं
a और b का लघुत्तम समापवर्त्य (least common multiple) वह सबसे छोटा धनात्मक मान है जो a और b दोनों से विभाज्य हो। इसे दूसरे तरीके से कहें, तो हमें ऐसा मान l (least common multiple) चाहिए, जिसके लिए a·x = l और b·y = l, जहाँ x और y धनात्मक पूर्णांक हैं (2 ≤ x, y)।एक सरल (naive) तरीक़ा यह होगा कि हम
a के बहुलकों (1·a, 2·a, 3·a, ...) को जाँचेें और देखें कि कौन-सा बहुलक b से भी विभाज्य है। हालाँकि, बहुत बड़े मानों के लिए यह प्रक्रिया बहुत लंबी हो सकती है। कल्पना कीजिए कि a और b की मानें 13 और 17 हों। तब हमें 1·13, 2·13, …, 17·13 तक जाँच करनी पड़ेगी, ताकि दोनों को विभाजित करने वाला कोई बहुलक मिले।असल में,
a·b हमेशा a और b का एक सामान्य बहुलक होता है, पर यह ज़रूरी नहीं कि यही सबसे छोटा हो। उदाहरण के तौर पर, 13 और 17 के लिए यह सबसे छोटा बहुलक है, लेकिन 8 और 12 जैसे कुछ मामलों में यह सबसे छोटा बहुलक नहीं होता। सामान्य रूप से, a और b का LCM (लघुत्तम समापवर्त्य) a · b को उनके GCD (महत्तम समापवर्तक) से भाग देने पर मिलता है:इस फ़ॉर्मूले के पीछे का तर्क यह है कि LCM दोनों संख्याओं का वह सबसे छोटा बहुलक है जिसमें उनकी सभी सांझा अभाज्य (prime) गुणांक शामिल होते हैं। चूँकि दो संख्याओं का GCD उन सभी सांझा अभाज्य गुणांकों का गुणनफल होता है, इसलिए
a·b को GCD से भाग देकर दोहराए गए अभाज्य गुणांकों को हटा दिया जाता है, जिसके परिणास्वरूप हमें ठीक-ठीक LCM प्राप्त होता है।अतः दो संख्याओं का LCM निकालने के लिए, हम पहले दोनों संख्याओं का अभाज्य गुणनखंड (prime factorization) ढूँढते हैं और फिर हर अभाज्य संख्या की उस अधिकतम घात को लेते हैं जो दोनों में से किसी एक में भी मौजूद हो, और उन्हें गुणा कर देते हैं।
यहाँ
a·b में दोनों संख्याओं के सभी अभाज्य गुणांक अपने-अपने घातों के योग के साथ आ जाते हैं, जबकि gcd(a, b) उन सामान्य अभाज्य गुणांकों की न्यूनतम घातों को घटा देता है। इस तरह आपके पास प्रत्येक गुणांक की अधिकतम घात बचती है, जो ठीक-ठीक LCM देने के लिए आवश्यक है।इनपुट
इनपुट की अकेली पंक्ति में दो पूर्णांक
a और b दिए जाते हैं (1 ≤ a, b ≤ )।आउटपुट
प्रोग्राम को
a और b का लघुत्तम समापवर्त्य प्रिंट करना चाहिए।Examples
Input | Output |
8 12 | 24 |
54 24 | 216 |
17 16 | 272 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB