B. The Golden Age——math

柔光的暖阳◎ 2022-06-14 01:47 144阅读 0赞

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

[Codeforces题目链接][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"

[Codeforces]: http://codeforces.com/problemset/problem/813/B