پیمان در دوران کودکی بسیار کنجکاو بود. پیرمرد بداخلاقی همسایه‌ی آن‌ها بود که خانه‌اش بسیار مرموز به نظر می‌رسید و حتی در ورودی آن با یک رمز دیجیتالی باز می‌شد. پیمان علاقه‌ی زیادی به دیدن داخل خانه داشت اما پیرمرد بسیار گوشه‌گیر بود و کسی را به خانه‌اش راه نمی‌داد. پس از اصرار بسیار، پیرمرد قبول کرد تا پیمان و خانواده‌اش را به خانه‌اش دعوت کند اما فقط در صورتی که او بتواند خودش رمز دیجیتالی را محاسبه و وارد کند. پیرمرد نحوه‌ی محاسبه‌ی رمز را به پیمان توضیح داد اما پیمان موفق به محاسبه‌ی آن نشد. حال پس از گذشت سال‌ها، پیمان از شما خواسته است که رمز را برای او محاسبه کنید.

دنباله‌ی تجزیه‌ی عدد $x$، دنباله‌ای صعودی از اعداد اول است که حاصل ضرب اعضای آن، $x$ باشد. برای مثال دنباله‌ی تجزیه‌ی عدد $60$، $(2, 2, 3, 5)$ است. به طور خاص دنباله‌ی تجزیه‌ی عدد $1$ تهی است. پیرمرد ابتدای هر سال یک عدد $n$ انتخاب می‌کند و با استفاده از آن رمز سال را به صورت زیر تولید می‌کند:

او ابتدا تمام زیرمجموعه‌های مجموعه‌ی اعداد $1$ تا $n$ را می‌نویسد و سپس برای هر زیرمجموعه، طول پیشوند مشترک دنباله‌های تجزیه‌ی اعضای آن را محاسبه می‌کند. در نهایت برای به دست آوردن رمز، این اعداد را با هم جمع می‌زند.

دنباله‌ی $A$ پیشوند دنباله‌ی $B$ است، اگر و فقط اگر دنباله‌ی $A$ دقیقا در ابتدای دنباله‌ی $B$ آمده باشد. پیشوند مشترک چند دنباله، بلندترین دنباله‌ای است که پیشوند تمام آن دنباله‌ها باشد. توجه کنید که این دنباله می‌تواند تهی باشد. برای مثال $(1, 2)$ پیشوند دنباله‌ی $(1, 2, 3, 4)$ است اما پیشوند دنباله‌ی $(1, 3, 4)$ نیست. پیشوند مشترک دنباله‌های $(2, 2, 3)$، $(2, 3, 3)$ و $(2, 3, 5)$، دنباله‌ی تک عضوی $(2)$ است. این دنباله‌ها به ترتیب دنباله‌ی عددهای $12$، $18$، و $30$ هستند و بنابراین به ازای مجموعه‌ی این اعداد، عدد یک در محاسبه‌ی رمز جمع زده می‌شود. همچنین چون پیشوند مشترک دنباله‌های $(2, 3)$ و $(3, 5)$ تهی است، به ازای مجموعه‌ی اعداد $6$، و $15$ عدد صفر در محاسبه‌ی رمز جمع زده می‌شود.

فرض کنید رمز حاصل با انتخاب عدد $n$ را با $f(n)$ نشان دهیم. به پیمان کمک کنید و به سوالات زیر پاسخ دهید.

تمام پاسخ‌های ارائه شده در این سوال با فرض $\Delta = 229939$ محاسبه شده‌اند.

$3$- الف ($11$ نمره) : باقی‌مانده‌ی $f(10)^3$ (به توان سه توجه کنید) بر $\Delta$ چند است؟

$3$- ب ($11$ نمره) : باقی‌مانده‌ی $f(1000)$ بر $\Delta$ چند است؟

$3$- ج ($11$ نمره) : باقی‌مانده‌ی $f(10^6)$ بر $\Delta$ چند است؟

• سوال قبل
• سوال بعد