পাইথনে চমৎকার বিভাজকের সংখ্যা সর্বাধিক করার জন্য প্রোগ্রাম

ধরুন আমাদের একটি সংখ্যা pf মৌলিক গুণনীয়ক সংখ্যা প্রতিনিধিত্ব করে. আমাদের একটি ধনাত্মক সংখ্যা n করতে হবে যা নিম্নলিখিত শর্তগুলি পূরণ করে −

n এর মৌলিক গুণনীয়ক সংখ্যা (স্বতন্ত্র হতে পারে বা নাও হতে পারে) সর্বাধিক 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 মোড 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))