المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله‌ی سوم:دوره‌ی ۲۰:سوال ۸

اول دوست

یک زیر عدد از عدد طبیعی و مثبت $x$، یک زیررشته‌ی متوالی از ارقام $x$ است. برای مثال، ۱۴۳ یک زیر عدد از ۱۱۴۳ است. اما ۹۲۱ یک زیر عدد از ۹۰۲۱۸ نیست. با این تعریف، یک عدد $n$ رقمی $n \times (n+1)/2$ زیر عدد (نه لزوما متمایز) دارد. ضمنا یک زیر عدد را معتبر می‌گوییم اگر با صفر شروع نشود.

فرض کنید $P(x)$ تعداد زیر عددهای معتبر عدد $x$ است که اول هم هستند. برای مثال $P(130312 )$ برابر ۶ است؛ زیرا از بین ۲۱ زیر عدد آن، تنها۱۷ تایش معتبرند (با صفر شروع نمی‌شوند) و از این ۱۷ تا، تنها ۶ تایش اول هستند که عبارتند از ۳،۲،۱۳،۳۱،۱۳۰۳ و ۳. دقت کنید که عدد ۳ دوبار شمرده شده است؛ یک بار برای زیر رشته شامل رقم دوم (از سمت چپ) و یک بار برای زیر رشته شامل رقم چهارم (از سمت چپ).

حاصل جمع خروجی تابع $P$ روی تمام اعداد کوچک‌تر از ۱۳۸۹۰۰۰ (یعنی $P(1)+P(2)+…+P(1389000)$) را $M$‌بگیرید. مقدار باقی‌مانده‌ی تقسیم $M$ بر $\Delta$ چند است؟


ابزار صفحه