अभाज्य गुणनखंडों की अधिकतम संख्या pf दी गई है। एक संख्या n बनाएं जिसके अभाज्य गुणनखंड ≤ pf हों, जिससे अच्छे भाजकों की संख्या अधिकतम हो। अच्छा भाजक = n के प्रत्येक अभाज्य गुणनखंड से विभाज्य भाजक।
गणितीय विश्लेषण
मान लीजिए n = p₁^a₁ × p₂^a₂ × ... × pₖ^aₖ जहां Σaᵢ ≤ pf।
अच्छे भाजक वे हैं जो प्रत्येक pᵢ से विभाज्य हैं, यानी रूप p₁^b₁ × ... × pₖ^bₖ जहां 1 ≤ bᵢ ≤ aᵢ।
अच्छे भाजकों की संख्या = a₁ × a₂ × ... × aₖ (गुणनखंड)।
इसे अधिकतम करना है जब Σaᵢ = pf दिया हो।
इष्टतम रणनीति
- गुणनफल अधिकतम होता है जब संख्याएं 3 के करीब हों (AM-GM असमानता)
- इसलिए अधिकतम संभव
3का उपयोग करें - शेष 0: सभी 3
- शेष 1: एक 3 को दो 2 में बदलें (3×1 < 2×2)
- शेष 2: एक 2 जोड़ें
Python कार्यान्वयन
def max_nice_divisors(pf):
MOD = 10**9 + 7
if pf == 1:
return 1
q, r = divmod(pf, 3)
if r == 0:
return pow(3, q, MOD)
elif r == 1:
# 3^(q-1) × 4
return pow(3, q - 1, MOD) * 4 % MOD
else: # r == 2
# 3^q × 2
return pow(3, q, MOD) * 2 % MOD
# परीक्षण
print(max_nice_divisors(5)) # 6
print(max_nice_divisors(1)) # 1
print(max_nice_divisors(2)) # 2
print(max_nice_divisors(3)) # 3
print(max_nice_divisors(4)) # 4 (2×2)
print(max_nice_divisors(6)) # 9 (3×3)
print(max_nice_divisors(7)) # 12 (3×2×2)
आउटपुट
6
1
2
3
4
9
12
उदाहरण pf=5
इष्टतम विभाजन: 3 + 2 = 5 → घातांक [3, 2] → अच्छे भाजक = 3×2 = 6
संख्या: n = p₁³ × p₂² (जैसे 2³ × 5² = 8 × 25 = 200)
अच्छे भाजक: 10, 20, 40, 50, 100, 200 (6 भाजक)
जटिलता
- समय: O(log pf) - मॉड्यूलर एक्सपोनेंशिएशन
- स्थान: O(1)
मुख्य बिंदु
- समस्या पूर्णांक विभाजन में अधिकतम गुणनफल तक कम हो जाती है
- 3 इष्टतम आधार है (e ≈ 2.718 के निकटतम पूर्णांक)
- शेष 1 के लिए 3+1 → 2+2 समायोजन
pow(base, exp, mod)कुशल मॉड्यूलर एक्सपोनेंशिएशन
