মনে করুন pf হল প্রাইম ফ্যাক্টরের সংখ্যা। আমাদের একটি পজিটিভ সংখ্যা n বানাতে হবে যা নিচের শর্তগুলো পূরণ করে −
n-এর প্রাইম ফ্যাক্টরের সংখ্যা (ডISTINCT হয় নাও হোক) hoogoto pf।
n-এর নাইস ডিভাইজার সংখ্যা সর্বোচ্চ। আমরা জানি n-এর একটি ডিভাইজার নাইস হয় যখন সেটি n-এর সব প্রাইম ফ্যাক্টর দ্বারা বিভাজ্য।
আমাদের n-এর নাইস ডিভাইজার সংখ্যা বের করতে হবে। যদি উত্তর খুব বড় হয় তবে মডুলো 10^9 + 7 দিয়ে রিটার্ন করুন।
সুতরাং, যদি ইনপুট হয় pf = 5, তবে আউটপুট হবে 6 কারণ n = 200 হলে প্রাইম ফ্যাক্টর [2,2,2,5,5] এবং এর নাইস ডিভাইজার [10,20,40,50,100,200] যাতে ৬টি ডিভাইজার।
এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব −
যদি pf == 1 হয়, তবে
1 রিটার্ন করুন
m := 10^9 + 7
q := pf/3-এর ভাগফল, r := pf mod 3
যদি r == 0 হয়, তবে
3^q mod m রিটার্ন করুন
অন্যথায় যখন r == 1 হয়, তবে
(3^(q-1) mod m)*4 mod m রিটার্ন করুন
অন্যথায়,
(3^q mod m)*2 mod m রিটার্ন করুন
উদাহরণ
বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশন দেখুন
def solve(pf):
if pf == 1:
return 1
m = 10**9 + 7
q, r = divmod(pf, 3)
if r == 0:
return pow(3, q, m)
elif r == 1:
return pow(3, q-1, m) * 4 % m
else:
return pow(3, q, m) * 2 % m
pf = 5
print(solve(pf))
ইনপুট
5
আউটপুট
6
