- محدودیت زمان: ۲ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
- آزمون عملی سوم فاینال سی و دومین دوره المپیاد کامپیوتر ایران
جک بعد از اینکه به دوستان المپیاد کامپیوتری خود خیانت کرد و به سمت المپیاد ریاضی رفت، در کلاس های المپیاد ریاضی ثبت نام کرد. در هفته اول ۳ کلاس جبر، ترکیبیات و نظریه اعداد داشت. در کلاس جبر با تابع و در کلاس نظریه اعداد با ب.م.م (بزرگترین مقسوم علیه مشترک) و در کلاس ترکیبیات با مفاهیم جایگشت آشنا شد.
حال او آموخته های خود را ترکیب کرده و تابع $f(x)$ را به شکل زیر ساخته است:
$f(x)$ برابر بزرگترین مقسوم علیه مشترک تمامی عددهایی است که ممکن است از جایگشت دادن ارقام عدد $x$ به دست بیاید؛ برای مثال برای عدد ۱۲۰، جایگشت‌های ممکن برابر $\langle 12, 21, 102, 120, 201, 210 \rangle$ است که ب.م.م آنها برابر ۳ است.
حال سوالی که برای جک پیش آمده این است که اگر به ازای همه‌ی اعداد ۱ تا $n$ مقدار $f(x)$ را حساب و جمع کنیم به چه عددی می‌رسیم؟
او این سوال را پیش دوستان المپیاد ریاضی خود مطرح کرد ولی دوستان او در حل این مسئله ناتوان بودند. او دست از پا درازتر پیش دوستان المپیاد کامپیوتری خود آمد و سوالش را به آنها گفت تا برایش حل کنند.
دوستان او از اینکه جک به آنها خیانت کرده بود، ناراحت بودند و به دنبال انتقام بودند؛ از این رو سوال او را دزدیدند و برای فاینال‌های عملی پیشنهاد دادند. از آنجا که سوال جک مورد قبول واقع شد، شما باید این سوال را حل کنید!
ورودی
در تنها خط ورودی عدد $n$ داده می‌شود. $$1 \leq n < 10^{5,001}$$
خروجی
در تنها خط خروجی جواب سوال جک یا همان $\displaystyle \sum_{i=1}^{n} f(i)$ را چاپ کنید.
زیرمسئله‌ها
| زیرمسئله | نمره | محدودیت |
|---|---|---|
| ۱ | ۸ | $n \leq 10^6$ |
| ۲ | ۳۵ | $n \leq 10^{18}$ |
| ۳ | ۲۹ | $n < 10^{501}$ |
| ۴ | ۲۸ | بدون محدودیت اضافی |
مثال
در اینجا چند نمونه برای فهم بهتر صورت سوال و قالب ورودی و خروجی تست‌ها داده می‌شود.
ورودی نمونه ۱
20
خروجی نمونه ۱
79
در مثال اول مقدار تابع به ازای اعداد یک‌رقمی و یازده برابر با خودشان، برای ۱۲ و ۱۵ برابر ۳، برای ۲۰ برابر ۲ و برای بقیه اعداد برابر ۱ است. پس حاصل به صورت کلی برابر ۷۹ خواهد بود.
ورودی نمونه ۲
123456
خروجی نمونه ۲
966228
ارسال پاسخ برای این سؤال