خوب من یه راه دی پی انه میزارم که راه به نسبت خوبیه:

خوب dp_i برابره با: dp تمام مقسوم علیه های i به جز خودش و

dp_1 برابر ۱ هستش.

خوب بقیشم که معلومه

کد زدنشم که کاری نداره(بدیهیه)

امیدوارم تونسته باشم کمکی کرده باشم!!

آپدیت:اینی که من گفتم شبیه بک ترک شده!!خودتون حواستون باشه dp بزنید...خخخخخخخخ

آپدیت بعدی:

برای حلش ابتدا بیاید تمام مقسوم علیه های n رو به صورت سورت شده تو یه جایی ذخیره کنیم.بعد از پایین شروع می کنیم میایم تا بالابه هرمقسوم علیه(i) که رسیدیم میایم تو ی بقیه ی مقسوم علیه ها میگردیم واونایی که مضرب i هستند رو آپدیت میکنیم مقدارشونو.

**اینو گفتم که بعدا نگید درست راه حلتو بگو!!

یه آپدیت واسه توضیح بیشتر:

خوب راهم رو با همون مثال توی سوال توضیح میدم:

نوشتن به اون روشی که سوال گفته ما میایم اولین عددی که باید بنویسیم رو مشخص میکنیم که میشه همه ی مقسوم علیه های اون عدد به جز یک.مثلا برای 12 میشه :2و3و4و6و12.در صورت انتخاب هر کدوم از اینا مقدار باقی مانده برای نوشتن میشه 12 تقسیم بر اون عدد یعنی:6و4و3و2و1.

این یعنی اینکه اگه ما عدد اول رو 2 انتخاب کردیم ، باید یه بار مسِله رو برای 6 حل کنیم (برای حل مسِله واسه عدد 6 هم دوباره از روش بالا استفاده می کنیم.)و این کار را تا موقعی انجام میدیم که به عدد اول برسیم که مقسوم علیه هاش 2 هست که اگه خودشو حساب نکنیم فقط یه مقسوم علیه داره که اونم 1 هست (که میدونیم تداد راه های نوشتن عدد 1 ، 1 هست)

پس برای 12 ما باید بیایم مسِله رو برای اعداد 1و2و3و4و6 حل کنیم.

برای 6 باید بیایم برای 1و2و3 حل کنیم.برای 4 باید 1و2 رو حل کنیم.(بقیه هم که اول هستند)

الان جواب برای عدد 12 میشه تعداد اعداد اول و 1 که توی راه حل بالا بهشون رسیدیم.(یه نگاه بندازید میفهمید 8 تاست)

یه نکته*:برای حل این سوال اینکه عدد اولمون چی باشه هیچ فرقی نمیکنه پس میتونیم اعداد اول بزرگ رو با اعداد اول کوچیکتر حل کرد.

یه نکته دیگه**:میتونیم بیایم توی کد زدن از یه روش دیگه استفاده کنیم که دیگه هیچ مشکلی پیش نیاد.سعی میکنم سری کدشو بزارم برای دوستان.

موفق باشید.

نخونید دوستان غلطه . میشه درستش کرد باید رو شمولش کار کرد ولی خیلی طولانی میشه. اگه کسی درست کرد بنویسه.

میدونیم که حداکثر تعداد اعداد برابره با مجموع توان های عوامل اول عدد اصلی که برای 12 برابر با 2+1=3 است. فرض کن عدد اصلی x باشه (اینجا 12) و مجموع توان های عوامل اولش y (اینجا 3 ) . حالا یه عامل اول در نظر بگیر و فرض کن توانش تو x برابر z باشه.

حالا فرض کن بخوای z تا از این عددو بین y تا مکان پخش کنی. که جوابش میشه تعداد جواب های معادله $a_1 + a_2 + ... + a_y = z$ که برابره با $\binom{z+y-1}{y-1} $ . برای بقیه عوامل اول هم همین کارو میکنیم و این عددها رو تو هم ضرب میکنیم.

اما ما حالت هایی که 1 توشون هست رو هم شمردیم پس باید کمشون کنیم.از اصل شمول و عدم شمول استفاده میکنیم و حالت هایی که یدونه 1 دارن رو کم میکنیم و حالت هایی که 2 تا یک دارن رو اضافه میکنیم و همینطور تا آخر . یعنی جواب نهایی اینه : $$\prod \binom{z+y-1}{y-1} -$$ $$\binom{y}{1} \prod \binom{z+y-2}{y-2}+ $$ $$ \binom{y}{2} \prod \binom{z+y-3}{y-3} - $$ $$ ... $$ الان مثال میزارم.