B. The Golden Age——math

Think: 1宏定义+sort排序+unique()去重函数+筛法 2题意理解:输入x,y,l,r寻找在区间[l, r]中不满足n = x^a + y^b的连续最长长度 3错误反思: 1>数组越界 2>存储的数据大小超出存储变量的存储范围 3>两端临界情况 4>l == r时的情况

Codeforces题目链接

B. The Golden Age time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output

Unlucky year in Berland is such a year that its number n can be represented as n = xa + yb, where a and b are non-negative integer numbers. For example, if x = 2 and y = 3 then the years 4 and 17 are unlucky (4 = 20 + 31, 17 = 23 + 32 = 24 + 30) and year 18 isn’t unlucky as there is no such representation for it. Such interval of years that there are no unlucky years in it is called The Golden Age. You should write a program which will find maximum length of The Golden Age which starts no earlier than the year l and ends no later than the year r. If all years in the interval [l, r] are unlucky then the answer is 0.

Input The first line contains four integer numbers x, y, l and r (2 ≤ x, y ≤ 1018, 1 ≤ l ≤ r ≤ 1018).

Output Print the maximum length of The Golden Age within the interval [l, r]. If all years in the interval [l, r] are unlucky then print 0. Examples

Input 2 3 1 10

Output 1

Input 3 5 10 22

Output 8

Input 2 3 3 5

Output 0

Note In the first example the unlucky years are 2, 3, 4, 5, 7, 9 and 10. So maximum length of The Golden Age is achived in the intervals [1, 1], [6, 6] and [8, 8]. In the second example the longest Golden Age is the interval [15, 22].

以下为Accepted代码

#include <bits/stdc++.h> #define LL long long int #define ULL unsigned long long int using namespace std; LL tp, link[40000]; int main() { LL x, y, l, r, i, j, ans, len; while(scanf("%lld %lld %lld %lld", &x, &y, &l, &r) != EOF) { tp = 0; for(i = 1; ; i *= x) { for(j = 1; ; j *= y) { if(i + j >= l && i + j <= r) { link[tp++] = i + j; } if(j > r/y) break; } if(i > r/x) break; } ans = 0; if(tp) { sort(link, link+tp); tp = unique(link, link+tp) - link; if(link[0] > l) { ans = max(ans, link[0]-l); } for(i = 1; i < tp; i++) { len = link[i] - link[i-1] - 1; ans = max(ans, len); } if(r > link[tp-1]) { ans = max(ans, r-link[tp-1]); } } else { ans = max(ans, r-l+1); } printf("%lld\n", ans); } return 0; }

以下为测试数据

→Judgement Protocol Test: #1, time: 0 ms., memory: 312 KB, exit code: 0, checker exit code: 0, verdict: OK Input 2 3 1 10 Output 1 Answer 1 Checker Log ok 1 number(s): "1" Test: #2, time: 0 ms., memory: 312 KB, exit code: 0, checker exit code: 0, verdict: OK Input 3 5 10 22 Output 8 Answer 8 Checker Log ok 1 number(s): "8" Test: #3, time: 0 ms., memory: 316 KB, exit code: 0, checker exit code: 0, verdict: OK Input 2 3 3 5 Output 0 Answer 0 Checker Log ok 1 number(s): "0" Test: #4, time: 15 ms., memory: 308 KB, exit code: 0, checker exit code: 0, verdict: OK Input 2 2 1 10 Output 1 Answer 1 Checker Log ok 1 number(s): "1" Test: #5, time: 0 ms., memory: 316 KB, exit code: 0, checker exit code: 0, verdict: OK Input 2 2 1 1000000 Output 213568 Answer 213568 Checker Log ok 1 number(s): "213568" Test: #6, time: 0 ms., memory: 320 KB, exit code: 0, checker exit code: 0, verdict: OK Input 2 2 1 1000000000000000000 Output 144115188075855871 Answer 144115188075855871 Checker Log ok 1 number(s): "144115188075855871" Test: #7, time: 0 ms., memory: 316 KB, exit code: 0, checker exit code: 0, verdict: OK Input 2 3 1 1000000 Output 206415 Answer 206415 Checker Log ok 1 number(s): "206415" Test: #8, time: 15 ms., memory: 312 KB, exit code: 0, checker exit code: 0, verdict: OK Input 2 3 1 1000000000000000000 Output 261485717957290893 Answer 261485717957290893 Checker Log ok 1 number(s): "261485717957290893" Test: #9, time: 0 ms., memory: 312 KB, exit code: 0, checker exit code: 0, verdict: OK Input 12345 54321 1 1000000 Output 933334 Answer 933334 Checker Log ok 1 number(s): "933334" Test: #10, time: 15 ms., memory: 308 KB, exit code: 0, checker exit code: 0, verdict: OK Input 54321 12345 1 1000000000000000000 Output 976614248345331214 Answer 976614248345331214 Checker Log ok 1 number(s): "976614248345331214" Test: #11, time: 0 ms., memory: 312 KB, exit code: 0, checker exit code: 0, verdict: OK Input 2 3 100000000 1000000000000 Output 188286357653 Answer 188286357653 Checker Log ok 1 number(s): "188286357653" Test: #12, time: 0 ms., memory: 316 KB, exit code: 0, checker exit code: 0, verdict: OK Input 2 14 732028847861235712 732028847861235712 Output 0 Answer 0 Checker Log ok 1 number(s): "0" Test: #13, time: 0 ms., memory: 316 KB, exit code: 0, checker exit code: 0, verdict: OK Input 14 2 732028847861235713 732028847861235713 Output 1 Answer 1 Checker Log ok 1 number(s): "1" Test: #14, time: 0 ms., memory: 320 KB, exit code: 0, checker exit code: 0, verdict: OK Input 3 2 6 7 Output 1 Answer 1 Checker Log ok 1 number(s): "1" Test: #15, time: 0 ms., memory: 316 KB, exit code: 0, checker exit code: 0, verdict: OK Input 16 5 821690667 821691481 Output 815 Answer 815 Checker Log ok 1 number(s): "815" Test: #16, time: 15 ms., memory: 316 KB, exit code: 0, checker exit code: 0, verdict: OK Input 1000000000000000000 2 1 1000000000000000000 Output 423539247696576511 Answer 423539247696576511 Checker Log ok 1 number(s): "423539247696576511" Test: #17, time: 0 ms., memory: 312 KB, exit code: 0, checker exit code: 0, verdict: OK Input 2 1000000000000000000 1000000000000000 1000000000000000000 Output 423539247696576511 Answer 423539247696576511 Checker Log ok 1 number(s): "423539247696576511" Test: #18, time: 15 ms., memory: 316 KB, exit code: 0, checker exit code: 0, verdict: OK Input 2 2 1000000000000000000 1000000000000000000 Output 1 Answer 1 Checker Log ok 1 number(s): "1" Test: #19, time: 0 ms., memory: 312 KB, exit code: 0, checker exit code: 0, verdict: OK Input 3 3 1 1 Output 1 Answer 1 Checker Log ok 1 number(s): "1" Test: #20, time: 0 ms., memory: 316 KB, exit code: 0, checker exit code: 0, verdict: OK Input 2 3 626492297402423196 726555387600422608 Output 100063090197999413 Answer 100063090197999413 Checker Log ok 1 number(s): "100063090197999413" Test: #21, time: 0 ms., memory: 316 KB, exit code: 0, checker exit code: 0, verdict: OK Input 4 4 1 1 Output 1 Answer 1 Checker Log ok 1 number(s): "1" Test: #22, time: 0 ms., memory: 316 KB, exit code: 0, checker exit code: 0, verdict: OK Input 304279187938024110 126610724244348052 78460471576735729 451077737144268785 Output 177668463693676057 Answer 177668463693676057 Checker Log ok 1 number(s): "177668463693676057" Test: #23, time: 0 ms., memory: 316 KB, exit code: 0, checker exit code: 0, verdict: OK Input 510000000000 510000000000 1 1000000000000000000 Output 999998980000000000 Answer 999998980000000000 Checker Log ok 1 number(s): "999998980000000000" Test: #24, time: 0 ms., memory: 316 KB, exit code: 0, checker exit code: 0, verdict: OK Input 2 10000000000000000 1 1000000000000000000 Output 413539247696576512 Answer 413539247696576512 Checker Log ok 1 number(s): "413539247696576512" Test: #25, time: 0 ms., memory: 316 KB, exit code: 0, checker exit code: 0, verdict: OK Input 84826654960259 220116531311479700 375314289098080160 890689132792406667 Output 515374843694326508 Answer 515374843694326508 Checker Log ok 1 number(s): "515374843694326508" Test: #26, time: 15 ms., memory: 316 KB, exit code: 0, checker exit code: 0, verdict: OK Input 1001 9999 1 1000000000000000000 Output 988998989390034998 Answer 988998989390034998 Checker Log ok 1 number(s): "988998989390034998" Test: #27, time: 0 ms., memory: 316 KB, exit code: 0, checker exit code: 0, verdict: OK Input 106561009498593483 3066011339919949 752858505287719337 958026822891358781 Output 205168317603639445 Answer 205168317603639445 Checker Log ok 1 number(s): "205168317603639445" Test: #28, time: 15 ms., memory: 320 KB, exit code: 0, checker exit code: 0, verdict: OK Input 650233444262690661 556292951587380938 715689923804218376 898772439356652923 Output 183082515552434548 Answer 183082515552434548 Checker Log ok 1 number(s): "183082515552434548" Test: #29, time: 0 ms., memory: 316 KB, exit code: 0, checker exit code: 0, verdict: OK Input 4294967297 4294967297 1 1000000000000000000 Output 999999991410065406 Answer 999999991410065406 Checker Log ok 1 number(s): "999999991410065406" Test: #30, time: 0 ms., memory: 316 KB, exit code: 0, checker exit code: 0, verdict: OK Input 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 Output 1 Answer 1 Checker Log ok 1 number(s): "1" Test: #31, time: 0 ms., memory: 312 KB, exit code: 0, checker exit code: 0, verdict: OK Input 2 2 1 1 Output 1 Answer 1 Checker Log ok 1 number(s): "1" Test: #32, time: 0 ms., memory: 316 KB, exit code: 0, checker exit code: 0, verdict: OK Input 73429332516742239 589598864615747534 555287238606698050 981268715519611449 Output 318240518387121676 Answer 318240518387121676 Checker Log ok 1 number(s): "318240518387121676" Test: #33, time: 0 ms., memory: 308 KB, exit code: 0, checker exit code: 0, verdict: OK Input 282060925969693883 446418005951342865 709861829378794811 826972744183396568 Output 98493812262359820 Answer 98493812262359820 Checker Log ok 1 number(s): "98493812262359820" Test: #34, time: 0 ms., memory: 316 KB, exit code: 0, checker exit code: 0, verdict: OK Input 97958277744315833 443452631396066615 33878596673318768 306383421710156519 Output 208425143965840685 Answer 208425143965840685 Checker Log ok 1 number(s): "208425143965840685" Test: #35, time: 0 ms., memory: 316 KB, exit code: 0, checker exit code: 0, verdict: OK Input 40975442958818854 7397733549114401 299774870238987084 658001214206968260 Output 358226343967981177 Answer 358226343967981177 Checker Log ok 1 number(s): "358226343967981177" Test: #36, time: 0 ms., memory: 316 KB, exit code: 0, checker exit code: 0, verdict: OK Input 699 700 1 1000 Output 697 Answer 697 Checker Log ok 1 number(s): "697" Test: #37, time: 0 ms., memory: 300 KB, exit code: 0, checker exit code: 0, verdict: OK Input 483076744475822225 425097332543006422 404961220953110704 826152774360856248 Output 343076029885034022 Answer 343076029885034022 Checker Log ok 1 number(s): "343076029885034022" Test: #38, time: 0 ms., memory: 316 KB, exit code: 0, checker exit code: 0, verdict: OK Input 4294967297 4294967297 1 999999999999999999 Output 999999991410065405 Answer 999999991410065405 Checker Log ok 1 number(s): "999999991410065405" Test: #39, time: 0 ms., memory: 308 KB, exit code: 0, checker exit code: 0, verdict: OK Input 702012794 124925148 2623100012 1000000000000000000 Output 491571744457491660 Answer 491571744457491660 Checker Log ok 1 number(s): "491571744457491660" Test: #40, time: 0 ms., memory: 312 KB, exit code: 0, checker exit code: 0, verdict: OK Input 433333986179614514 1000000000000000000 433333986179614515 726628630292055493 Output 293294644112440978 Answer 293294644112440978 Checker Log ok 1 number(s): "293294644112440978" Test: #41, time: 15 ms., memory: 320 KB, exit code: 0, checker exit code: 0, verdict: OK Input 999999999999999999 364973116927770629 4 4 Output 1 Answer 1 Checker Log ok 1 number(s): "1" Test: #42, time: 0 ms., memory: 308 KB, exit code: 0, checker exit code: 0, verdict: OK Input 4 2 40 812 Output 191 Answer 191 Checker Log ok 1 number(s): "191" Test: #43, time: 0 ms., memory: 316 KB, exit code: 0, checker exit code: 0, verdict: OK Input 2 3 1 1 Output 1 Answer 1 Checker Log ok 1 number(s): "1" Test: #44, time: 0 ms., memory: 316 KB, exit code: 0, checker exit code: 0, verdict: OK Input 1556368728 1110129598 120230736 1258235681 Output 989898863 Answer 989898863 Checker Log ok 1 number(s): "989898863" Test: #45, time: 0 ms., memory: 312 KB, exit code: 0, checker exit code: 0, verdict: OK Input 7 9 164249007852879073 459223650245359577 Output 229336748650748455 Answer 229336748650748455 Checker Log ok 1 number(s): "229336748650748455" Test: #46, time: 0 ms., memory: 312 KB, exit code: 0, checker exit code: 0, verdict: OK Input 324693328712373699 541961409169732375 513851377473048715 873677521504257312 Output 324693328712373697 Answer 324693328712373697 Checker Log ok 1 number(s): "324693328712373697" Test: #47, time: 15 ms., memory: 312 KB, exit code: 0, checker exit code: 0, verdict: OK Input 370083000139673112 230227213530985315 476750241623737312 746365058930029530 Output 146054845259371103 Answer 146054845259371103 Checker Log ok 1 number(s): "146054845259371103" Test: #48, time: 15 ms., memory: 316 KB, exit code: 0, checker exit code: 0, verdict: OK Input 4 3 584 899 Output 146 Answer 146 Checker Log ok 1 number(s): "146" Test: #49, time: 0 ms., memory: 320 KB, exit code: 0, checker exit code: 0, verdict: OK Input 4 3 286 581 Output 161 Answer 161 Checker Log ok 1 number(s): "161" Test: #50, time: 15 ms., memory: 316 KB, exit code: 0, checker exit code: 0, verdict: OK Input 304045744870965151 464630021384225732 142628934177558000 844155070300317027 Output 304045744870965149 Answer 304045744870965149 Checker Log ok 1 number(s): "304045744870965149" Test: #51, time: 0 ms., memory: 312 KB, exit code: 0, checker exit code: 0, verdict: OK Input 195627622825327857 666148746663834172 1 1000000000000000000 Output 470521123838506314 Answer 470521123838506314 Checker Log ok 1 number(s): "470521123838506314" Test: #52, time: 0 ms., memory: 312 KB, exit code: 0, checker exit code: 0, verdict: OK Input 459168731438725410 459955118458373596 410157890472128901 669197645706452507 Output 209242527248078910 Answer 209242527248078910 Checker Log ok 1 number(s): "209242527248078910" Test: #53, time: 0 ms., memory: 312 KB, exit code: 0, checker exit code: 0, verdict: OK Input 999999999999999999 999999999999999999 1 1000000000000000000 Output 999999999999999997 Answer 999999999999999997 Checker Log ok 1 number(s): "999999999999999997" Test: #54, time: 0 ms., memory: 320 KB, exit code: 0, checker exit code: 0, verdict: OK Input 752299248283963354 680566564599126819 73681814274367577 960486443362068685 Output 606884750324759243 Answer 606884750324759243 Checker Log ok 1 number(s): "606884750324759243" Test: #55, time: 0 ms., memory: 316 KB, exit code: 0, checker exit code: 0, verdict: OK Input 20373217421623606 233158243228114207 97091516440255589 395722640217125926 Output 142191179567388113 Answer 142191179567388113 Checker Log ok 1 number(s): "142191179567388113" Test: #56, time: 0 ms., memory: 304 KB, exit code: 0, checker exit code: 0, verdict: OK Input 203004070900 20036005000 1 1000000000000000000 Output 999999776959924100 Answer 999999776959924100 Checker Log ok 1 number(s): "999999776959924100" Test: #57, time: 0 ms., memory: 316 KB, exit code: 0, checker exit code: 0, verdict: OK Input 565269817339236857 318270460838647700 914534538271870694 956123707310168659 Output 41589169038297966 Answer 41589169038297966 Checker Log ok 1 number(s): "41589169038297966" Test: #58, time: 15 ms., memory: 312 KB, exit code: 0, checker exit code: 0, verdict: OK Input 2 5 330 669 Output 131 Answer 131 Checker Log ok 1 number(s): "131" Test: #59, time: 15 ms., memory: 316 KB, exit code: 0, checker exit code: 0, verdict: OK Input 9 9 91 547 Output 385 Answer 385 Checker Log ok 1 number(s): "385" Test: #60, time: 15 ms., memory: 308 KB, exit code: 0, checker exit code: 0, verdict: OK Input 9 4 866389615074294253 992899492208527253 Output 126509877134233001 Answer 126509877134233001 Checker Log ok 1 number(s): "126509877134233001" Test: #61, time: 0 ms., memory: 312 KB, exit code: 0, checker exit code: 0, verdict: OK Input 3037000500 3037000500 1 1000000000000000000 Output 999999993925999000 Answer 999999993925999000 Checker Log ok 1 number(s): "999999993925999000" Test: #62, time: 0 ms., memory: 312 KB, exit code: 0, checker exit code: 0, verdict: OK Input 4294967297 4294967297 12 1000000000000000000 Output 999999991410065406 Answer 999999991410065406 Checker Log ok 1 number(s): "999999991410065406" Test: #63, time: 0 ms., memory: 316 KB, exit code: 0, checker exit code: 0, verdict: OK Input 5 3 78510497842978003 917156799600023483 Output 238418579101562499 Answer 238418579101562499 Checker Log ok 1 number(s): "238418579101562499" Test: #64, time: 0 ms., memory: 312 KB, exit code: 0, checker exit code: 0, verdict: OK Input 749206377024033575 287723056504284448 387669391392789697 931234393488075794 Output 361536985631243879 Answer 361536985631243879 Checker Log ok 1 number(s): "361536985631243879" Test: #65, time: 15 ms., memory: 316 KB, exit code: 0, checker exit code: 0, verdict: OK Input 999999999999999999 454135 1000000000000000000 1000000000000000000 Output 0 Answer 0 Checker Log ok 1 number(s): "0" Test: #66, time: 0 ms., memory: 312 KB, exit code: 0, checker exit code: 0, verdict: OK Input 759826429841877401 105086867783910112 667080043736858072 797465019478234768 Output 92746386105019330 Answer 92746386105019330 Checker Log ok 1 number(s): "92746386105019330" Test: #67, time: 15 ms., memory: 316 KB, exit code: 0, checker exit code: 0, verdict: OK Input 1000000000000000000 1000000000000000000 5 7 Output 3 Answer 3 Checker Log ok 1 number(s): "3" Test: #68, time: 0 ms., memory: 312 KB, exit code: 0, checker exit code: 0, verdict: OK Input 440968000218771383 43378854522801881 169393324037146024 995429539593716237 Output 511082684852142973 Answer 511082684852142973 Checker Log ok 1 number(s): "511082684852142973" Test: #69, time: 0 ms., memory: 312 KB, exit code: 0, checker exit code: 0, verdict: OK Input 15049917793417622 113425474361704411 87565655389309185 803955352361026671 Output 675479960205904638 Answer 675479960205904638 Checker Log ok 1 number(s): "675479960205904638" Test: #70, time: 15 ms., memory: 316 KB, exit code: 0, checker exit code: 0, verdict: OK Input 4 6 264626841724745187 925995096479842591 Output 369878143059623936 Answer 369878143059623936 Checker Log ok 1 number(s): "369878143059623936" Test: #71, time: 0 ms., memory: 316 KB, exit code: 0, checker exit code: 0, verdict: OK Input 4294967297 4294967297 13 1000000000000000000 Output 999999991410065406 Answer 999999991410065406 Checker Log ok 1 number(s): "999999991410065406" Test: #72, time: 15 ms., memory: 316 KB, exit code: 0, checker exit code: 0, verdict: OK Input 315729630349763416 22614591055604717 66895291338255006 947444311481017774 Output 609100090075649641 Answer 609100090075649641 Checker Log ok 1 number(s): "609100090075649641" Test: #73, time: 15 ms., memory: 316 KB, exit code: 0, checker exit code: 0, verdict: OK Input 3 10 173 739 Output 386 Answer 386 Checker Log ok 1 number(s): "386" Test: #74, time: 0 ms., memory: 316 KB, exit code: 0, checker exit code: 0, verdict: OK Input 161309010783040325 128259041753158864 5843045875031294 854024306926137845 Output 564456254389938656 Answer 564456254389938656 Checker Log ok 1 number(s): "564456254389938656" Test: #75, time: 0 ms., memory: 316 KB, exit code: 0, checker exit code: 0, verdict: OK Input 239838434825939759 805278168279318096 202337849919104640 672893754916863788 Output 433055320090924028 Answer 433055320090924028 Checker Log ok 1 number(s): "433055320090924028" Test: #76, time: 0 ms., memory: 316 KB, exit code: 0, checker exit code: 0, verdict: OK Input 9 9 435779695685310822 697902619874412541 Output 262122924189101720 Answer 262122924189101720 Checker Log ok 1 number(s): "262122924189101720" Test: #77, time: 0 ms., memory: 316 KB, exit code: 0, checker exit code: 0, verdict: OK Input 967302429573451368 723751675006196376 143219686319239751 266477897142546404 Output 123258210823306654 Answer 123258210823306654 Checker Log ok 1 number(s): "123258210823306654"