در شهر اعداد، دو عدد p و q وجود دارند . عدد p نسبت به عدد q حسودی میکند ، چون فکر میکند تعداد بیشتری عدد وجود دارد که بزرگترین توان q آنها بیشتر از بزرگترین توان p آنهاست. ما به کمک شما احتیاج داریم تا به p اثبات کنیم که حرف او لزوماً درست نیست.
فرض کنید f(a,b) برابر با بزرگترین (t≥0) باشد که a بر bt بخشپذیر باشد. به عدد x میگوییم خوب اگر f(x,p) بیشتر از f(x,q) باشد.
به شما چهار عدد a، b، p و q داده شده است ، شما باید تعداد اعداد خوب بزرگتر یا مساوی a و کمتر یا مساوی b را بیابید.
در سطر اول ورودی چهار عدد 1≤a≤b≤1018 و 2≤p,q≤109 آمده است.
در تنها سطر خروجی پاسخ سوال را چاپ نمایید.
ورودی نمونه | خروجی نمونه |
---|---|
1 20 3 2 | 4 |