توضیح الگوریتم:

امتیاز-n یک عدد را تعداد باقی مانده های متفاوت توان های آن عدد در تقسیم بر $n$ مینامیم. برای مثال امتیاز-5 عدد $3$ برابر $4$ است زیرا:

$3^1\equiv 3\pmod 5$ $,$ $3^2\equiv 4\pmod 5$ $,$ $3^3\equiv 2\pmod 5$ $,$ $3^4\equiv 1\pmod 5$

و از توان چهار به بعد همین الگو ادامه میابد. پس در واقع هدف ما در این سوال پیدا کردن مجموع امتیاز-1111151 تمام اعداد 1 تا 1111150 است.

حال برای پیدا کردن پاسخ امتیاز-1111151 های همه ی اعداد طبیعی کوچکتر از $1111151$ را بدست می آوریم.

از آنجا که عدد $1111151$ یک عدد اول است با توجه به قضیه ی کوچک فرما به ازای هر عدد $i$ که $(1 \le i <1111151)$ داریم:

$i^{1111150}\equiv 1\pmod {1111151}$

پس درواقع امتیاز-1111151 تمام اعداد طبیعی کوچکتر از $1111151$ باید مقسوم علیه عدد $1111150$ باشد.(زیرا بعد از باقیمانده ی $1$ باقیمانده دوباره به عدد $i$ میرسد و دوره ی گردش دوباره تکرار میشود تا به عدد $1111151$ برسد.)در نتیجه به ازای هر $i$ که $(1 \le i <1111151)$ قطعا عددی مانند $x$ پیدا میشود که کمترین مقدار ممکن باشد و :

$1111150 \equiv 0\pmod {x}$ $,$ $i^{x}\equiv 1\pmod {1111151}$

پس در واقع عدد $x$ همان امتیاز-1111151 عدد $i$ است.

از آنجا که عدد $1111150$ تنها $24$ مقسوم علیه دارد میتوانیم به ازای تمام اعداد طبیعی کوچکتر از $1111151$ امتیاز-1111151 آنها را پیدا کنیم و زمان زیادی هم طول نکشد. مجموع این امتیاز-1111151 ها جواب مسئله است.

توضیح کد:

در کد نوشته شده تابع modi برای گرفتن باقیمانده است. وکتور v مقسوم علیه های عدد 1111150 را در خود ذخیره می کند و تابع PowerUnderN نیز دو عدد $q$ و $w$ را به عنوان ورودی می گیرد و عدد $n$ $mod$ $q^w$ را به عنوان خروجی میدهد.

حدود زمان اجرای کد: 7800 ms

حدود مموری کد: 4 KB

مشاهده ی کد (C++)

جواب آخر: 821