ب.م.م

به یک مجموعه از اعداد صحیح $1$ تا $n$ خوب گفته می‌شود اگر و تنها اگر ب.م.م اعضای آن برابر $1$ نباشد. همچنین مجموعه تهی نیز یک مجموعه خوب است.

آشمز یک مجموعه $S$ در اختیار دارد که در ابتدا تهی است. هر روز مشتی یک عدد رندوم $x\notin S$ که $1\leq x\leq n$ انتخاب کرده و به آشمز می‌دهد و آشمز هم عدد $x$ را به مجموعه $S$ اضافه می‌کند. می‌دانیم اگر بعد از یک مرحله مجموعه $S$ دیگر خوب نباشد، آشمز خیلی ناراحت می‌شود. به همین دلیل مشتی هر روز عدد $x$ را از بین اعدادی که آشمز را ناراحت نمی‌کنند به صورت تصادفی و با احتمال برابر انتخاب می‌کند. زمانی که عدد $x\notin S$ وجود نداشته باشد که با اضافه کردن آن آشمز ناراحت نشود، عملیات را متوقف می‌کند.

حال شما به عنوان یک المپیاد کامپیوتری باید امید ریاضی تعداد اعضای مجموعه $S$ را پس از پایان عملیات‌های مشتی محاسبه کنید.

می‌توان نشان داد جواب به صورت یک کسر ساده‌نشدنی $\frac{P}{Q}$ است. شما باید مقدار $P\cdot Q^{-1}$ به پیمانه $\Delta$ را محاسبه کنید.

به عنوان مثال فرض کنید مقدار $n$ برابر $5$ است. در روز اول مجموعه $S$ تهی است و مشتی می‌تواند هر کدام از اعداد $2$ تا $5$ را با احتمال $\frac{1}{4}$ انتخاب کند. به احتمال $\frac{2}{4}$ عدد انتخاب شده $3$ یا $5$ است و روز بعد مشتی نمی‌تواند عدد دیگری اضافه کند که نسبت به $3$ یا $5$ اول نباشد. در نتیجه در این حالت عملیات مشتی پس از $1$ روز به پایان می‌رسد. به احتمال $\frac{2}{4}$ یکی از اعداد $2$ یا $4$ انتخاب شده و در روز بعد هم مشتی عدد دیگر را انتخاب می‌کند. پس به احتمال $\frac{2}{4}$ اندازه مجموعه نهایی برابر $1$ و به احتمال $\frac{2}{4}$ اندازه مجموعه نهایی برابر $2$ است. در نتیجه جواب برابر است با $\frac{3}{2}$.

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

$1$- الف ($21$ نمره) : جواب سوال را به ازای $n=15$ به پیمانه $\Delta$ خروجی دهید.

$1$- ب ($31$ نمره) : جواب سوال را به ازای $n=500$ به پیمانه $\Delta$ خروجی دهید.

$1$- ج ($24$ نمره) : جواب سوال را به ازای $n=5\,000$ به پیمانه $\Delta$ خروجی دهید.

$1$- د ($24$ نمره) : جواب سوال را به ازای $n=3\,000\,000$ به پیمانه $\Delta$ خروجی دهید.