12620 - Fibonacci Sum

[sdipu]

Can anyone please tell me AC output for following input:

Code: Select all

12
1 1
1 1000
1 200
1 300
1 1000000000000
1000 10000
1000 1000
500000 5000000
1000000000000 100000000000000 
25 30
55 55
1245 1234668783

[brianfry713]

Code: Select all

1
49475
9950
14800
49333333333475
444075
75
222000025
4884000000000075
216
45
60910265682

[sdipu]

Thanks brianfry713. But I am still getting WA. Here is my code:

I've found the sequence repeats from 300th term. So I pre-calculated sum of terms up to 300.
I've checked several test cases. But I can't see why I could get WA.

Code: Select all

ACCEPTED :D 

[brianfry713]

Input:

Code: Select all

100
551645919 1525894733
227294622 528297243
726850682 937802578
123368976 1673043620
18629692 1060875493
295967012 1613486201
179153954 312073650
95837721 207198682
865364700 2087442010
1333239700 1926374745
436180289 646618526
574737998 1500673852
1578940643 1875827444
481860949 637924091
47080131 165903909
1691798643 1919836154
14567653 143041047
252639519 828204105
353764078 1027500432
884163323 1204212601
670215154 1433269264
1745342914 1850345491
221768161 262253715
202212077 1841180635
69221278 775425226
1422043752 1535451778
333255081 555386900
283730697 1996781750
167123214 320098978
486002887 765591646
537944152 700206235
24664441 30317882
19928086 838593901
1866094333 1924090907
980819860 1212286066
498071682 1806986610
1509848453 1651035014
90600699 95930948
517202604 1419908979
47850557 2115500807
93769268 1409699668
495192259 1469894309
96056046 244627272
58058155 101333618
866925264 1806414605
359137192 1050729137
1081047020 1404869416
95979669 1202384474
978991733 1939569008
1004371426 1962074003
1621576965 1959811593
1463362959 1502443108
614432284 983941771
256367102 1229168041
1197185201 1388001992
41782693 304217659
114600495 553170490
329976827 467820934
569154552 945820731
604751688 1362524012
265769502 1436079816
693465584 963888880
18789706 1346816522
349456628 789445253
604035608 997781439
810109384 2143273308
13783155 78128926
54161121 125988696
406033560 949123176
189641521 1318437799
3222294 404858290
118169246 839859534
58396689 1249283778
47620861 1755826543
970866908 1876835020
513058637 652372550
379625019 1236636410
435969284 1858896772
500858377 1635051137
485348928 1574871166
465766839 1104893986
1183022912 1295458313
500037062 921409946
15943844 97609961
157807562 629120098
1033978389 2060174643
752550529 891219570
148496177 1992007170
1600350065 2060230997
1397641 40640561
269279785 423733325
45309915 807529909
33570348 161790894
1796842031 2096339019
503925125 1019801411
104085717 134707311
483261908 946903715
708078999 1160234661
553715636 704128985
1333249084 1591363136

AC output:

Code: Select all

48062941550
14849462788
10406960238
76450615554
51417459717
64997613419
6557371679
5493807677
60289146943
29261328672
10381619391
45679501946
14646415295
7699115488
5861972730
11249850684
6338020852
28394519698
33237660016
15789097934
37644002643
5180127253
1997287116
80855782278
34839394515
5594796187
10958503160
84510518400
7546804675
13793044995
8004929669
278903342
40387513469
2861164372
11418999655
64573136372
6965203515
262958900
44533514576
102004079005
64919233266
48085301044
7329513784
2134922998
46348140548
34118536048
15975238138
54582637172
47388478543
47246660612
16686241642
1927953985
18229134633
47991513160
9413628391
12946791569
21636119957
6800309116
18582198180
37383434738
57735308832
13340882606
65515989530
21706105391
19424794507
65769420220
3174391269
3543494038
26792421228
55687283165
19814042799
35603387579
58750429490
84271480289
44694427202
6872819455
42279228704
70197756222
55953509572
53749763987
31530272901
5546813127
20787729109
4028862147
23251418658
50625681650
6841006224
90946542525
22687459613
1935984196
7619707920
37602853527
6325547248
14775184737
25449896465
1510665374
22872996263
22306346042
7420392191
12733626434

[sdipu]

Thanks for your test data, brianfry713. You are a great helper.

[acmh]

Hello, can anyone help me?
I pre-calculated sum of terms up to 300 too.
So,
IF (N >= 1 && M <= 300) the answer is the sum of fib[N] until fib[M]
ELSE
I calculated N % 300 (I called NN) and M % 300 (NM)
And My answer is the sum of fib[NN] until fib[300] (Doing this I "complete" the interval)
plus fib[1] until fib[NM] (Close the interval)
plus ( (N + 300 - NN) + (M - NM) )/300*the sum of fib[1] until fib[300] (How many complete intervals I have times the sum complete interval)

For example, If I have N = 288 and M = 603
I sum fib[288] until fib[300] (I will call this A), after that sum fib[1] until fib[3] (and call this B);
So, N + 300 - NN == 300 and (M - NM) == 600 then (600 - 300)/300 == 1 ( I have one complete cycle between the parameters)
Then I did the math described above.

[brianfry713]

It looks like you figured it out.