محدودیت زمان: ۲ ثانیه محدودیت حافظه: ۲۵۶ مگابایت آی مجری که به فکر بچهها است، یادش رفته…
- User
محدودیت زمان: ۲ ثانیه محدودیت حافظه: ۲۵۶ مگابایت آی مجری که به فکر بچهها است، یادش رفته است که به فکر بچهها است! او به جای قصهی شبانگاهی میخواهد یک بازی راه بیاندازد تا بچهها به سر کار بروند(فردا متوجه این موضوع میشوید) و خودش راحت بخوابد. او یک رشته بزرگ به بچهها میدهد که فقط از ارقام تشکیل شده است. سپس از آنها میخواهد که تعداد زیر رشتههای این رشته را پیدا کنند که اگر این زیر رشته را به عنوان یک عدد در نظر بگیریم، این عدد بر عدد اول p p بخش پذیر است. اگر کسی جواب درست را بدهد، آی مجری به او به اندازهی آن عدد شیرینی خواهد داد. متاسفانه از آنجایی که بچهها جواب این سوال را نمیدانند، سعی میکنند که هی عدد بپرانند تا اینکه آی مجری بگوید که درست گفتهاند و شیرینیها را به آنها بدهد؛ اما برای اینکه شیرینی بیشتری بگیرند تلاش میکنند که عددهای بزرگی را به عنوان جواب به آی مجری بگویند غافل از اینکه جواب عدد بزرگی نیست... آنها هی عدد میپرانند و آی مجری مجبور است که به آنها بگوید که جوابشان درست است یا خیر و اینگونه است که نمیتواند بخوابد و چون اعداد بچهها از جواب خیلی دور است متاسفانه آی مجری به این زودیها نمیتواند بخوابد. حالا آی مجری از ایدهاش پشیمان شده است و میخواهد خود جواب را بگوید و به همه شیرینی بدهد و مثل همیشه برایشان قصه بخواند تا خوابشان ببرد و او هم بتواند بخوابد اما متاسفانه الان دیر وقت است و او جواب را یادش نمیآید. به او کمک کنید که جواب را پیدا کند.
ورودی ورودی شامل دو خط است که در خط اول رشته مورد نظر میآید و در خط دوم عدد اول p p. 2 ≤ p ≤ 1 0 9 2≤p≤10 9
طول رشته حداکثر 1 0 6 10 6 میباشد. رشته تنها از ارقام تشکیل شده است.
خروجی در تنها سطر خروجی تعداد زیررشتههایی از رشتهی ورودی را خروجی دهید که عدد متناظر با آن زیر رشته بر p p بخش پذیر است.
مثال ورودی نمونه ۱ 3146 3 Plain text خروجی نمونه ۱ 2 Plain text ورودی نمونه ۲ 1313 13 Plain text خروجی نمونه ۲ 3 c++
- Assistant
برای حل این مسئله باید تعداد زیررشتههایی از رشته عددی داده شده را که قابل تقسیم بر عدد اول ( p ) هستند، پیدا کنیم. بسته به مقدار ( p ) که میتواند یکی از اعداد اول ۲ یا ۵ باشد یا مقداری دیگر از این بازه باشد، روش مختلفی را اعمال میکنیم.
روش عملکرد:
-
اگر ( p = 2 ) یا ( p = 5 ):
- عددی به عدد از رشته را بررسی میکنیم که اگر آخرین رقم آن:
- برای ( p = 2 ): رقم آخر عدد زوج باشد.
- برای ( p = 5 ): رقم آخر عدد ۰ یا ۵ باشد.
- در این صورت، تعداد زیررشتههای ممکن که با این شرط مطابقت دارند، با اضافه کردن تعداد زیررشتههای تماماً حاوی آن رقم به جواب نهایی افزوده میشود.
- عددی به عدد از رشته را بررسی میکنیم که اگر آخرین رقم آن:
-
اگر ( p ) برابر با ۲ یا ۵ نباشد:
- از مفهوم باقیماندههای پیشوندی استفاده میکنیم. با محاسبه باقیمانده هر زیررشته از تقسیم بر ( p )، تعداد زیررشتههایی که باقیمانده صفر دارند را شمارش میکنیم.
- برای این منظور، از یک دیکشنری استفاده میکنیم که تعداد دفعات باقیماندههای پیشوندی را ذخیره میکند.
پیادهسازی:
در ادامه پیادهسازی این روشها در زبان پایتون آورده شده است:
import sys import sys from collections import defaultdict def main(): import sys import sys S = sys.stdin.readline().strip() p_line = sys.stdin.readline().strip() while p_line == '': p_line = sys.stdin.readline().strip() p = int(p_line) N = len(S) if p ==2 or p==5: result=0 for i in range(N): d = int(S[i]) if p ==2: if d %2 ==0: result +=i+1 else: # p==5 if d ==0 or d ==5: result +=i+1 print(result) else: if p ==1: # Not needed since p >=2 print(0) return counts = defaultdict(int) counts[0] =1 current=0 power=1 result=0 for i in range(N-1,-1,-1): d = int(S[i]) current = (d * power + current) %p result += counts[current] counts[current] +=1 power = (power *10) %p print(result) if __name__ == "__main__": main()توضیح کد:
-
ورودی خواندن:
- رشته عددی ( S ) و عدد ( p ) به ترتیب از ورودی خوانده میشوند.
-
بررسی مقدار ( p ):
- اگر ( p ) برابر ۲ یا ۵ باشد، از روش شرطی استفاده میکنیم و تعداد زیررشتههایی که آخرین رقم آنها زوج (برای ( p = 2 )) یا صفر و پنج (برای ( p = 5 )) است را شمارش میکنیم.
- اگر ( p ) برابر با ۲ یا ۵ نباشد، از روش پیشوندی استفاده میکنیم:
- از انتهای رشته به ابتدا حرکت میکنیم.
- باقیمانده هر زیررشته از تقسیم بر ( p ) را محاسبه میکنیم و تعداد دفعات دیده شدن آن باقیمانده را در دیکشنری
countsذخیره میکنیم. - تعداد زیررشتههای قابل تقسیم بر ( p ) را به صورت تجمعی محاسبه میکنیم.
مثالها:
-
ورودی نمونه ۱:
3146 3خروجی:
2 -
ورودی نمونه ۲:
1313 13خروجی:
3
این کد با دقت بالا و بهینه برای مواجهه با رشتههای طولانی و اعداد ( p ) بزرگ طراحی شده است.
-