+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- *علی که حسابی از کار کشاورزی سود کرده... تصمیم گرفت یک شرکت با هدف موتور جست و جوی کالا، تاسیس کند و به یاد مرحوم ترب، نام آن را ترب گذاشته...* *تربچه تصمیم گرفته در این شرکت استخدام شود برای همین می‌خواهد در آزمون استخدامی شرکت کند. در این آزمون سوال زیر آمده... به تربچه کمک کنید تا این سوال را حل کند.* در این سوال یک دنباله از اعداد طبیعی مانند $a_1, a_2, a_3, ..., a_n\ $ آمده است و از تربچه خواسته شده تا حاصل عبارت زیر را محاسبه کند. $$ \sum_{i=1}^{n}\sum_{j=1}^{n}\lfloor\frac{a_i}{a_j}\rfloor$$ به تربچه کمک کنید تا این عبارت را محاسبه کند و در شرکت ترب استخدام شود. # ورودی در سطر اول ورودی عدد صحیح $n$ که نشان دهنده تعداد اعداد دنباله است و در سطر دوم $n$ عدد صحیح با فاصله آمده که عدد $i$ام نشان دهنده مقدار $a_i$ است. $$1 \le n, a_i \le 100\ 000$$ # خروجی در تنها سطر خروجی، یک عدد صحیح که پاسخ مسئله است را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 3 1 2 3 ``` ## خروجی نمونه ۱ ``` 9 ``` حاصل عبارت برابر است با: $$\lfloor\frac{1}{1}\rfloor + \lfloor\frac{1}{2}\rfloor + \lfloor\frac{1}{3}\rfloor + \lfloor\frac{2}{1}\rfloor + \lfloor\frac{2}{2}\rfloor + \lfloor\frac{2}{3}\rfloor + \lfloor\frac{3}{1}\rfloor + \lfloor\frac{3}{2}\rfloor + \lfloor\frac{3}{3}\rfloor =$$ $$ 1 + 0 + 0 + 2 + 1 + 0 + 3 + 1 + 1 = 9$$ ## ورودی نمونه ۲ ``` 4 1 1 1 1 ``` ## خروجی نمونه ۲ ``` 16 ``` چون همه مقادیر باهم برابر است حاصل عبارت برابر است با: $$4 \times 4 \times \lfloor\frac{1}{1}\rfloor = 16$$ # قسمت آموزشی در این قسمت راهنمایی‌های سوال، به مرور اضافه می‌شود. مشکلات‌تان در راستای حل سوال را می‌توانید از بخش ["سوال بپرسید"](https://quera.ir/contest/clarification/19378/) مطرح کنید. <details class="blue"> <summary>راهنمایی ۱</summary> فرض کنید مقدار $\lfloor\frac{a_i}{a_j}\rfloor = k$ در این صورت داریم $$k \leq \frac{a_i}{a_j} < k + 1 \Rightarrow k a_j \leq a_i \leq (k + 1) a_j $$ مقدار $M$ را بزرگ ترین عدد آمده در دنباله در نظر بگیرید یعنی: $$M = \max_{1 \le i \le n}\{ a_i \}$$ مقدار $cnt_k$ را تعریف می‌کنیم تعداد همه $a_i$ هایی که $a_i < k$ باشد. به راحتی می‌توان مقدار $cnt_k$ را برای همه $1 \le k \le max\{a_i\}$ از مرتبه زمانی $O(M)$ با استفاده از ایده جمع تجمعی یا `partial sum` محاسبه کرد. </details> <details class="blue"> <summary>راهنمایی ۲</summary> مقدار خواسته شده را با حالت بندی روی $k$های مختلف محاسبه می‌کنیم. $$\sum_{i=1}^{n}\sum_{j=1}^{n} \lfloor\frac{a_i}{a_j}\rfloor = \sum_{j=1}^{n} \sum_{k=1}^{max\{a_i\}} k(cnt_{(k + 1)a_j} - cnt_{ka_j})$$ با کمی مشاهده متوجه می‌شویم نیازی نیست مجموع دوم تا انتهای کار محاسبه شود (چرا؟). و همین که $k \leq \frac{M}{a_j}$ باشید کافی است پس داریم : $$ = \sum_{j = 1}^{n}\sum_{k = 1}^{\frac{M}{a_j}} k(cnt_{(k + 1)a_j} - cnt_{ka_j}) $$ </details> <details class="blue"> <summary>راهنمایی ۳</summary> به جای مجموع روی اندیس $a_j$ روی مقدار $a_j$ مجموع را حساب می‌کنیم یعنی اگر $a_j = l$ باشد داریم: $$ = \sum_{l = 1}^{M}\sum_{k=1}^{\frac{M}{l}} k(cnt_{(k + 1)a_j} - cnt_{ka_j})$$ همانطور که می‌دانیم دو مجموع فوق مشابه الگوریتم غربال-اراتستن از مرتبه زمانی $O(M \log{M})$ بنابراین کل مسئله از مرتبه زمانی $O(n + M \log{M})$ حل می‌شود. </details>

حل سؤال در بانک سؤالات