المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی سوم:دوره ی ۲۵:سوال ۶

معلم مینگو

مینگو یک مجموعه به نام $S$ از اعداد طبیعی 1 تا $n$ دارد. به ازای هر $A \subseteq S$، $F(A)$ را این‌گونه تعریف می‌کنیم: $$F(A)=\{x=\frac{b}{a}~ |~ a,b\in A, x \in \mathbb{N},x>1\}$$

که $\mathbb{N}=\{1,2,3,\ldots\}$ مجموعه‌ی اعداد طبیعی می‌باشد.

اگر $Y_1, Y_2, \ldots, Y_{2^n}$ همه‌ی $2^n$ زیرمجموعه‌ی $S$ باشند، معلم مینگو از او خواسته تا مقدار زیر را محاسبه کند: $$X=\sum_{i=1}^{2^n} |F(Y_i)|$$ نکته: $|F(Y_i)|$ نشان‌دهنده‌ی تعداد اعضای مجموعه‌ی $F(Y_i)$ می‌باشد.

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

$6$- الف ($10$ نمره) : باقی‌مانده‌ی $X$ بر $\Delta$ به ازای $n=20$ چند است؟

پاسخ

8816

$6$- ب ($12$ نمره) : باقی‌مانده‌ی $X$ بر $\Delta$ به ازای $n=1000$ چند است؟

پاسخ

10061

$6$- ج ($15$ نمره) : باقی‌مانده‌ی $X$ بر $\Delta$ به ازای $n=10^6$ چند است؟

پاسخ

10544


ابزار صفحه