सभी चुनौतियाँ
मध्यम 0 हल किए गए 0% स्वीकृति

ऑयलर टोशिएंट फलन

1 से n तक के उन पूर्णांकों को गिनिए जिनका n के साथ कोई उभयनिष्ठ गुणनखंड नहीं है।

आप क्या सीखेंगे

  • n के अलग-अलग अभाज्य गुणनखंड ढूँढना
  • केवल पूर्णांकों से φ(n) = n × Π(1 − 1/p) लागू करना
  • n = 1 और अभाज्य n को संभालना

समस्या

ऑयलर का टोशिएंट फलन φ(n) उन पूर्णांकों k को गिनता है जिनके लिए 1 ≤ k ≤ n और gcd(k, n) = 1 हो। उदाहरण के लिए, φ(9) = 6, क्योंकि 1, 2, 4, 5, 7 और 8 का 9 के साथ कोई उभयनिष्ठ गुणनखंड नहीं है।

eulers_totient(n) लिखिए।

n 10^12 तक हो सकता है, इसलिए एक-एक k गिनना बहुत धीमा है। इसकी बजाय गुणनफल सूत्र इस्तेमाल कीजिए: φ(n) = n × (1 − 1/p), जहाँ गुणा n को विभाजित करने वाली हर अलग अभाज्य संख्या p के लिए होता है। इसे पूर्णांकों में n / p × (p − 1) के रूप में करने से भिन्नों से बचा जा सकता है।

इनपुट

n: एक धनात्मक पूर्णांक।

आउटपुट

φ(n) लौटाइए। परिभाषा के अनुसार φ(1) = 1।

सीमाएँ

1 ≤ n ≤ 10^12

उदाहरण

उदाहरण 1
इनपुट:
n = 36

अपेक्षित आउटपुट:
expected = 12
इनपुट:
long long n = 36;

अपेक्षित आउटपुट:
long long expected = 12;
इनपुट:
long n = 36;

अपेक्षित आउटपुट:
long expected = 12;

व्याख्या

36 = 2² × 3², इसलिए φ(36) = 36 × (1 − 1/2) × (1 − 1/3) = 36 × 1/2 × 2/3 = 12।

उदाहरण 2
इनपुट:
n = 13

अपेक्षित आउटपुट:
expected = 12
इनपुट:
long long n = 13;

अपेक्षित आउटपुट:
long long expected = 12;
इनपुट:
long n = 13;

अपेक्षित आउटपुट:
long expected = 12;

व्याख्या

13 अभाज्य है, इसलिए 1 से 12 तक का हर k उसके साथ सह-अभाज्य (coprime) है और φ(13) = 12।

कैसे हल करें

पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।

संकेत 1

√n तक trial division से n के गुणनखंड निकालिए।

संकेत 2

हर अलग अभाज्य p के लिए परिणाम को परिणाम / p × (p − 1) से बदलिए; पहले भाग दीजिए ताकि मान छोटा रहे।

संकेत 3

लूप के बाद 1 से बड़ा बचा गुणनखंड भी एक अभाज्य संख्या है।

अपेक्षित जटिलता

समय O(√n), अतिरिक्त स्थान O(1)

संदर्भ

यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।

हर कोडर का सबसे अच्छा पास हुआ समाधान। तेज़, कम मेमोरी वाले और बेहतर रेटिंग वाले समाधान ऊपर रहते हैं।

अभी कोई पास हुआ समाधान नहीं है। इसे हल करें और पहला स्थान पाएँ।

दूसरों से सीखें

समुदाय समाधान

अभी तक कोई प्रकाशित समाधान नहीं। पहला साझा करने के लिए इस चुनौती को हल करें।