समस्या
ऑयलर का टोशिएंट फलन φ(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
उदाहरण
इनपुट:
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।
इनपुट:
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 के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।