سلام

این سوالی که میگم سر حل دو تا سوال به ذهنم رسیده بود. سر قسمت ج سوال ۳ کانتست اول کدشارک به حل کردن این مساله رسیدم و سر حل قسمت ج سوال ۳ کانتست سوم کد شارک هم مساله به این ساده سازی میشد ولی اونجا هم حل نشد. (مِن باب دوستان نابغه بگم که حل این دو تا رو نمیخوام اینی که میگمو حل کنید !)

آرایه ای از اعداد داریم : a_1, a_2, a_3, ..., a_n که n<=100000

آرایه ی b_1, b_2, b_3, ..., b_n را بسازید به طوری که b_i برابر حاصل جمع a_j هایی است که j<=i و همچنین i و j نسبت به هم اولند.

(اگه کسی خواست ببینه اون دو تا سوال چجوری به این میرسیدن بگه همینجا اضافه کنم)

خب لازم شد اضافه کنم این بالایی رو :|

به عنوان مثال سوال ۳ قسمت ج آزمون سوم کد شارک (خب ببینید صورت سوالو بد نیست !)

راه حلم اینطوری بود که یه داینامیک میزدم به این صورت که d_i_j برابر است با جواب سوال اگر تعداد اعضای دنباله برابر 2^i (دو به توان آی) باشد و ب.م.م اعضای آن دقیقا j باشد. حالا میخوایم d_i_j رو پر کنیم. فرض کنید دنباله به طول 2^i را به دو دنباله با طول های برابر 2^(i-1) تقسیم کنیم. فرض کنید ب.م.م اعضای اولی a باشد و ب.م.م اعضای دومی b باشد. باید ب.م.م a و b برابر j شود. واضح است که هر دوی a و b باید بر j بخشپذیر باشند. پس با توجه به اینها ب.م.م a/j و b/j برابر ۱ است. حالا به این صورت عمل میکنیم که برای پر کردن d_i_j تمام d_(i-1)_k هایی که k بر j بخشپذیر است را در یک وکتور میریزیم و حالا فرض کنید این وکتور همان آرایه ی a در سوال بالاست. (از یک اندیس گذازی شده دیگه دقیقا مثل a) فرض کنید بتوان وکتور b را همانطور که صورت سوال خواسته برای این وکتور بسازیم. حالا اگر به ازای هر k بتوانیم d_(i-1)_j*k x b_k را محاسبه کنیم و جمع کنیم و حاصل را در دو ضرب کنیم و منهای d_(i-1)_1 ^ 2 بکنیم به مقدار d_i_j میرسیم :))))

اگه اثبات هم میخواید بگما ولی خودتون به اثباتش برسید خوب بهتره دیگه :)