Back
Close

Divisibility of Fibonacci numbers sum

Statement

 Goal

Sum of consecutive big Fibonacci numbers is divisible or not?

Let a, b and d non negative integers.
Determine if d divides F_a + F_{a+1} + F_{a+2} + … + F_b.

The difficulty is that we ask that for some very big indices a.

Remember that the well-known Fibonacci numbers is a sequence of numbers starting with 0 and 1, and after that each number is the sum of the two previous ones.

F_0 = 0
F_1 = 1
F_{n+2} = F_{n+1} + F_n

So the first Fibonacci numbers are:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233…

Example:
a = 10
b = 12
F_10 + F_11 + F_12 = 55 + 89 + 144 = 288 = 32 * 9 = 2^5 * 3^2

This sum is divisible by d = 2, 4, 8, 16 and 32, but NOT by 64.
This sum is divisible by d = 3 and 9, but NOT by 27.
This sum is NOT divisible by d = 5.
This sum is divisible by d = 6.
…

Example of input:
2
10 12 3
10 12 5

And the expected output:
F_10 + ... + F_12 is divisible by 3
F_10 + ... + F_12 is NOT divisible by 5

(When a = b write in the same way the beginning "F_a + ... + F_b"
even if there is only one term.)

Hints:
Implementations of Fibonacci numbers computation is an usual example about recursivity and algorithmic complexity. The obvious way to implement it with recursion is a classical example of complexity explosion. There is several way to fix that, and the most obvious is the simple iteration that compute the result in a linear number of steps (if we consider that operations on numbers are in constant time, which is not really the case). The key point to solve this challenge is to find a mathematical way to be better than that and to implement it.
To help you can read the "Matrix form" section in "Fibonacci number" article on Wikipedia:
https://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form

Maybe this list of the first 300 Fibonacci numbers and their factorization can help you:
http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibtable.html#100
But if you need these big numbers, you are probably on a wrong way. ;-)

Enjoy!

(If you are interested by the mathematical aspect, there exist a lot of nice properties about this sequence:
https://oeis.org/A000045 )

(The illustration image is a part of one page of the Liber Abaci:
https://commons.wikimedia.org/wiki/File:Liber_abbaci_magliab_f124r.jpg )
Input
Line 1: An non negative integer nb for the number of tests.

Next nb lines: Three space separated non negative integers a, b and d for the first index, for the last index, and for the divisor.
Output
nb lines:
"F_a + ... + F_b is divisible by d"
or
"F_a + ... + F_b is NOT divisible by d"
Constraints
1 ≤ nb ≤ 30
0 ≤ a ≤ b ≤ 1,000,000,000
b - a ≤ 10,000,000
1 ≤ d ≤ 1,000,000,000
Example
Input
13
10 12 2
10 12 32
10 12 64
10 12 3
10 12 9
10 12 27
10 12 5
10 12 7
10 12 11
10 12 287
10 12 288
10 12 289
10 12 1000
Output
F_10 + ... + F_12 is divisible by 2
F_10 + ... + F_12 is divisible by 32
F_10 + ... + F_12 is NOT divisible by 64
F_10 + ... + F_12 is divisible by 3
F_10 + ... + F_12 is divisible by 9
F_10 + ... + F_12 is NOT divisible by 27
F_10 + ... + F_12 is NOT divisible by 5
F_10 + ... + F_12 is NOT divisible by 7
F_10 + ... + F_12 is NOT divisible by 11
F_10 + ... + F_12 is NOT divisible by 287
F_10 + ... + F_12 is divisible by 288
F_10 + ... + F_12 is NOT divisible by 289
F_10 + ... + F_12 is NOT divisible by 1000

Tags
RecursionLoopsArithmeticModular calculus

Difficulty
Hard

Test cases
First example Test
Input
13 10 12 2 10 12 32 10 12 64 10 12 3 10 12 9 10 12 27 10 12 5 10 12 7 10 12 11 10 12 287 10 12 288 10 12 289 10 12 1000
Output
F_10 + ... + F_12 is divisible by 2 F_10 + ... + F_12 is divisible by 32 F_10 + ... + F_12 is NOT divisible by 64 F_10 + ... + F_12 is divisible by 3 F_10 + ... + F_12 is divisible by 9 F_10 + ... + F_12 is NOT divisible by 27 F_10 + ... + F_12 is NOT divisible by 5 F_10 + ... + F_12 is NOT divisible by 7 F_10 + ... + F_12 is NOT divisible by 11 F_10 + ... + F_12 is NOT divisible by 287 F_10 + ... + F_12 is divisible by 288 F_10 + ... + F_12 is NOT divisible by 289 F_10 + ... + F_12 is NOT divisible by 1000

Example Validator
Input
12 16 18 2 16 18 16 16 18 32 16 18 3 16 18 5 16 18 17 16 18 19 16 18 23 16 18 1000 16 18 5167 16 18 5168 16 18 5169
Output
F_16 + ... + F_18 is divisible by 2 F_16 + ... + F_18 is divisible by 16 F_16 + ... + F_18 is NOT divisible by 32 F_16 + ... + F_18 is NOT divisible by 3 F_16 + ... + F_18 is NOT divisible by 5 F_16 + ... + F_18 is divisible by 17 F_16 + ... + F_18 is divisible by 19 F_16 + ... + F_18 is NOT divisible by 23 F_16 + ... + F_18 is NOT divisible by 1000 F_16 + ... + F_18 is NOT divisible by 5167 F_16 + ... + F_18 is divisible by 5168 F_16 + ... + F_18 is NOT divisible by 5169

Other example Test
Input
24 0 10 1 0 10 1000 0 10 2 0 10 3 0 10 5 0 10 7 0 10 11 0 10 13 0 10 17 0 10 142 0 10 143 0 10 144 5 16 1 5 16 16 5 16 32 5 16 3 5 16 5 5 16 7 5 16 23 5 16 529 5 16 49 5 16 2575 5 16 2576 5 16 2577
Output
F_0 + ... + F_10 is divisible by 1 F_0 + ... + F_10 is NOT divisible by 1000 F_0 + ... + F_10 is NOT divisible by 2 F_0 + ... + F_10 is NOT divisible by 3 F_0 + ... + F_10 is NOT divisible by 5 F_0 + ... + F_10 is NOT divisible by 7 F_0 + ... + F_10 is divisible by 11 F_0 + ... + F_10 is divisible by 13 F_0 + ... + F_10 is NOT divisible by 17 F_0 + ... + F_10 is NOT divisible by 142 F_0 + ... + F_10 is divisible by 143 F_0 + ... + F_10 is NOT divisible by 144 F_5 + ... + F_16 is divisible by 1 F_5 + ... + F_16 is divisible by 16 F_5 + ... + F_16 is NOT divisible by 32 F_5 + ... + F_16 is NOT divisible by 3 F_5 + ... + F_16 is NOT divisible by 5 F_5 + ... + F_16 is divisible by 7 F_5 + ... + F_16 is divisible by 23 F_5 + ... + F_16 is NOT divisible by 529 F_5 + ... + F_16 is NOT divisible by 49 F_5 + ... + F_16 is NOT divisible by 2575 F_5 + ... + F_16 is divisible by 2576 F_5 + ... + F_16 is NOT divisible by 2577

Other example Validator
Input
25 4 19 1 4 19 3 4 19 9 4 19 5 4 19 7 4 19 49 4 19 11 4 19 521 4 19 271441 4 19 10940 4 19 10941 4 19 10942 0 12 1 0 12 1000 0 12 8 0 12 16 0 12 3 0 12 5 0 12 7 0 12 46 0 12 47 0 12 48 0 12 375 0 12 376 0 12 377
Output
F_4 + ... + F_19 is divisible by 1 F_4 + ... + F_19 is divisible by 3 F_4 + ... + F_19 is NOT divisible by 9 F_4 + ... + F_19 is NOT divisible by 5 F_4 + ... + F_19 is divisible by 7 F_4 + ... + F_19 is NOT divisible by 49 F_4 + ... + F_19 is NOT divisible by 11 F_4 + ... + F_19 is divisible by 521 F_4 + ... + F_19 is NOT divisible by 271441 F_4 + ... + F_19 is NOT divisible by 10940 F_4 + ... + F_19 is divisible by 10941 F_4 + ... + F_19 is NOT divisible by 10942 F_0 + ... + F_12 is divisible by 1 F_0 + ... + F_12 is NOT divisible by 1000 F_0 + ... + F_12 is divisible by 8 F_0 + ... + F_12 is NOT divisible by 16 F_0 + ... + F_12 is NOT divisible by 3 F_0 + ... + F_12 is NOT divisible by 5 F_0 + ... + F_12 is NOT divisible by 7 F_0 + ... + F_12 is NOT divisible by 46 F_0 + ... + F_12 is divisible by 47 F_0 + ... + F_12 is NOT divisible by 48 F_0 + ... + F_12 is NOT divisible by 375 F_0 + ... + F_12 is divisible by 376 F_0 + ... + F_12 is NOT divisible by 377

Big numbers Test
Input
25 32 85 43 20 100 4 32 85 45 20 100 3 32 85 2521 20 100 5 20 100 25 32 85 128 20 100 11 32 85 25 20 100 121 20 100 41 32 85 31 20 100 4577887 32 85 64 32 85 9 32 85 27 20 100 1174951 32 85 5 20 100 2 32 85 7 32 85 13 32 85 61 32 85 17 32 85 19
Output
F_32 + ... + F_85 is NOT divisible by 43 F_20 + ... + F_100 is NOT divisible by 4 F_32 + ... + F_85 is divisible by 45 F_20 + ... + F_100 is divisible by 3 F_32 + ... + F_85 is divisible by 2521 F_20 + ... + F_100 is divisible by 5 F_20 + ... + F_100 is NOT divisible by 25 F_32 + ... + F_85 is NOT divisible by 128 F_20 + ... + F_100 is divisible by 11 F_32 + ... + F_85 is NOT divisible by 25 F_20 + ... + F_100 is NOT divisible by 121 F_20 + ... + F_100 is divisible by 41 F_32 + ... + F_85 is divisible by 31 F_20 + ... + F_100 is divisible by 4577887 F_32 + ... + F_85 is divisible by 64 F_32 + ... + F_85 is divisible by 9 F_32 + ... + F_85 is NOT divisible by 27 F_20 + ... + F_100 is divisible by 1174951 F_32 + ... + F_85 is divisible by 5 F_20 + ... + F_100 is divisible by 2 F_32 + ... + F_85 is NOT divisible by 7 F_32 + ... + F_85 is NOT divisible by 13 F_32 + ... + F_85 is divisible by 61 F_32 + ... + F_85 is NOT divisible by 17 F_32 + ... + F_85 is divisible by 19

Big numbers Validator
Input
24 23 106 169 23 106 16 21 105 419 23 106 32 21 105 379 23 106 7 21 105 351 23 106 11 23 106 13 23 106 29 23 106 841 21 105 13 23 106 43 23 106 177241 23 106 5 21 105 2 23 106 9 21 105 4 21 105 27 21 105 81 21 105 11 23 106 27 21 105 421 21 105 10891
Output
F_23 + ... + F_106 is NOT divisible by 169 F_23 + ... + F_106 is divisible by 16 F_21 + ... + F_105 is NOT divisible by 419 F_23 + ... + F_106 is NOT divisible by 32 F_21 + ... + F_105 is divisible by 379 F_23 + ... + F_106 is NOT divisible by 7 F_21 + ... + F_105 is divisible by 351 F_23 + ... + F_106 is NOT divisible by 11 F_23 + ... + F_106 is divisible by 13 F_23 + ... + F_106 is divisible by 29 F_23 + ... + F_106 is NOT divisible by 841 F_21 + ... + F_105 is divisible by 13 F_23 + ... + F_106 is divisible by 43 F_23 + ... + F_106 is NOT divisible by 177241 F_23 + ... + F_106 is NOT divisible by 5 F_21 + ... + F_105 is divisible by 2 F_23 + ... + F_106 is divisible by 9 F_21 + ... + F_105 is NOT divisible by 4 F_21 + ... + F_105 is divisible by 27 F_21 + ... + F_105 is NOT divisible by 81 F_21 + ... + F_105 is NOT divisible by 11 F_23 + ... + F_106 is NOT divisible by 27 F_21 + ... + F_105 is divisible by 421 F_21 + ... + F_105 is divisible by 10891

Even big numbers Test
Input
23 123 234 343 123 234 2401 123 234 26013 123 234 3 123 234 78039 123 234 5 110 301 1024 123 234 103680 123 234 103682 123 234 20641 110 301 512 123 234 103681 110 301 1097 110 301 3167 211 398 43759 353 616 6561 211 398 43763 353 616 122464 353 616 5021024 211 398 81 353 616 19683 432 433 106998173 321 321 6
Output
F_123 + ... + F_234 is divisible by 343 F_123 + ... + F_234 is NOT divisible by 2401 F_123 + ... + F_234 is divisible by 26013 F_123 + ... + F_234 is divisible by 3 F_123 + ... + F_234 is NOT divisible by 78039 F_123 + ... + F_234 is NOT divisible by 5 F_110 + ... + F_301 is NOT divisible by 1024 F_123 + ... + F_234 is NOT divisible by 103680 F_123 + ... + F_234 is NOT divisible by 103682 F_123 + ... + F_234 is divisible by 20641 F_110 + ... + F_301 is divisible by 512 F_123 + ... + F_234 is divisible by 103681 F_110 + ... + F_301 is NOT divisible by 1097 F_110 + ... + F_301 is divisible by 3167 F_211 + ... + F_398 is NOT divisible by 43759 F_353 + ... + F_616 is divisible by 6561 F_211 + ... + F_398 is divisible by 43763 F_353 + ... + F_616 is divisible by 122464 F_353 + ... + F_616 is NOT divisible by 5021024 F_211 + ... + F_398 is NOT divisible by 81 F_353 + ... + F_616 is NOT divisible by 19683 F_432 + ... + F_433 is divisible by 106998173 F_321 + ... + F_321 is NOT divisible by 6

Even big numbers Validator
Input
23 121 240 32 121 240 2522 121 240 5 121 240 121 121 240 2521 121 240 31 121 240 25 121 240 11 121 240 6355441 102 305 8 121 240 81 102 305 16 121 240 61 121 240 281 345 602 17108701 102 305 9168377 345 602 500 121 240 2520 345 602 17165711 102 305 27505131 345 602 100 450 451 12854199 354 354 24
Output
F_121 + ... + F_240 is NOT divisible by 32 F_121 + ... + F_240 is NOT divisible by 2522 F_121 + ... + F_240 is divisible by 5 F_121 + ... + F_240 is NOT divisible by 121 F_121 + ... + F_240 is divisible by 2521 F_121 + ... + F_240 is divisible by 31 F_121 + ... + F_240 is NOT divisible by 25 F_121 + ... + F_240 is divisible by 11 F_121 + ... + F_240 is NOT divisible by 6355441 F_102 + ... + F_305 is divisible by 8 F_121 + ... + F_240 is NOT divisible by 81 F_102 + ... + F_305 is NOT divisible by 16 F_121 + ... + F_240 is divisible by 61 F_121 + ... + F_240 is divisible by 281 F_345 + ... + F_602 is divisible by 17108701 F_102 + ... + F_305 is divisible by 9168377 F_345 + ... + F_602 is NOT divisible by 500 F_121 + ... + F_240 is NOT divisible by 2520 F_345 + ... + F_602 is NOT divisible by 17165711 F_102 + ... + F_305 is NOT divisible by 27505131 F_345 + ... + F_602 is divisible by 100 F_450 + ... + F_451 is divisible by 12854199 F_354 + ... + F_354 is NOT divisible by 24

Larger indices Test
Input
16 1234 2345 4 3897 3910 54988205 1781 2444 9 1234 2345 6 1234 2345 36 3560 4013 15 1781 2444 2529 1234 2345 3 2123 4489 12810074 1234 2345 9 1234 2345 8 2123 4489 25620148 1234 2345 5 1234 2345 7 1234 2345 15 1781 2444 18
Output
F_1234 + ... + F_2345 is divisible by 4 F_3897 + ... + F_3910 is divisible by 54988205 F_1781 + ... + F_2444 is divisible by 9 F_1234 + ... + F_2345 is divisible by 6 F_1234 + ... + F_2345 is NOT divisible by 36 F_3560 + ... + F_4013 is NOT divisible by 15 F_1781 + ... + F_2444 is divisible by 2529 F_1234 + ... + F_2345 is divisible by 3 F_2123 + ... + F_4489 is divisible by 12810074 F_1234 + ... + F_2345 is NOT divisible by 9 F_1234 + ... + F_2345 is NOT divisible by 8 F_2123 + ... + F_4489 is NOT divisible by 25620148 F_1234 + ... + F_2345 is NOT divisible by 5 F_1234 + ... + F_2345 is NOT divisible by 7 F_1234 + ... + F_2345 is NOT divisible by 15 F_1781 + ... + F_2444 is NOT divisible by 18

Larger indices Validator
Input
14 1230 2343 32 1111 2222 68379666 2156 4860 15 3048 4482 12 1230 2343 1789 1230 2343 27 3604 6705 6158652 1230 2343 5 1230 2343 108 1111 2222 205138998 1230 2343 36 1230 2343 9 1230 2343 15 1230 2343 16
Output
F_1230 + ... + F_2343 is NOT divisible by 32 F_1111 + ... + F_2222 is divisible by 68379666 F_2156 + ... + F_4860 is NOT divisible by 15 F_3048 + ... + F_4482 is NOT divisible by 12 F_1230 + ... + F_2343 is divisible by 1789 F_1230 + ... + F_2343 is NOT divisible by 27 F_3604 + ... + F_6705 is divisible by 6158652 F_1230 + ... + F_2343 is NOT divisible by 5 F_1230 + ... + F_2343 is NOT divisible by 108 F_1111 + ... + F_2222 is NOT divisible by 205138998 F_1230 + ... + F_2343 is divisible by 36 F_1230 + ... + F_2343 is divisible by 9 F_1230 + ... + F_2343 is NOT divisible by 15 F_1230 + ... + F_2343 is divisible by 16

Even larger indices Test
Input
13 12345 23456 2 12345 23456 27 12378 64506 2659000 40045 70000 4023361 12345 23456 7 28090 34708 282609 21568 554433 1488436 12345 23456 81 12345 23456 5 34890 40566 243296 12345 23456 16 12345 23456 32 12345 23456 3
Output
F_12345 + ... + F_23456 is divisible by 2 F_12345 + ... + F_23456 is divisible by 27 F_12378 + ... + F_64506 is NOT divisible by 2659000 F_40045 + ... + F_70000 is divisible by 4023361 F_12345 + ... + F_23456 is NOT divisible by 7 F_28090 + ... + F_34708 is divisible by 282609 F_21568 + ... + F_554433 is divisible by 1488436 F_12345 + ... + F_23456 is NOT divisible by 81 F_12345 + ... + F_23456 is NOT divisible by 5 F_34890 + ... + F_40566 is NOT divisible by 243296 F_12345 + ... + F_23456 is divisible by 16 F_12345 + ... + F_23456 is NOT divisible by 32 F_12345 + ... + F_23456 is divisible by 3

Even larger indices Validator
Input
19 10347 60451 29 10347 60451 58 12347 23458 2 12347 23458 32 12347 23458 64 12347 23458 3 12347 23458 9 12347 23458 27 12347 23458 5 12347 23458 7 12347 23458 2207 12347 23458 2777 12347 23458 3167 20570 54895 72774368 20570 54895 145548736 34891 41254 218921379 34891 41254 656764137 39800 60456 861 39800 60456 4305
Output
F_10347 + ... + F_60451 is divisible by 29 F_10347 + ... + F_60451 is NOT divisible by 58 F_12347 + ... + F_23458 is divisible by 2 F_12347 + ... + F_23458 is divisible by 32 F_12347 + ... + F_23458 is NOT divisible by 64 F_12347 + ... + F_23458 is divisible by 3 F_12347 + ... + F_23458 is divisible by 9 F_12347 + ... + F_23458 is NOT divisible by 27 F_12347 + ... + F_23458 is NOT divisible by 5 F_12347 + ... + F_23458 is NOT divisible by 7 F_12347 + ... + F_23458 is divisible by 2207 F_12347 + ... + F_23458 is divisible by 2777 F_12347 + ... + F_23458 is divisible by 3167 F_20570 + ... + F_54895 is divisible by 72774368 F_20570 + ... + F_54895 is NOT divisible by 145548736 F_34891 + ... + F_41254 is divisible by 218921379 F_34891 + ... + F_41254 is NOT divisible by 656764137 F_39800 + ... + F_60456 is divisible by 861 F_39800 + ... + F_60456 is NOT divisible by 4305

Become really big Test
Input
20 654321 987654 4 489 1005 258282 654321 987654 3 2468 897089 74400513 654321 987654 55592635 654321 987654 17 489 1005 774846 654321 987654 5 48903 4680607 1399681 654321 987654 289 780613 980156 30 654321 987654 54289 48903 4680607 9797767 654321 987654 53 2468 897089 87927879 654321 987654 2809 654321 987654 11881 780613 980156 6 654321 987654 7647985 654321 987654 29717
Output
F_654321 + ... + F_987654 is NOT divisible by 4 F_489 + ... + F_1005 is divisible by 258282 F_654321 + ... + F_987654 is NOT divisible by 3 F_2468 + ... + F_897089 is divisible by 74400513 F_654321 + ... + F_987654 is NOT divisible by 55592635 F_654321 + ... + F_987654 is divisible by 17 F_489 + ... + F_1005 is NOT divisible by 774846 F_654321 + ... + F_987654 is NOT divisible by 5 F_48903 + ... + F_4680607 is divisible by 1399681 F_654321 + ... + F_987654 is NOT divisible by 289 F_780613 + ... + F_980156 is NOT divisible by 30 F_654321 + ... + F_987654 is NOT divisible by 54289 F_48903 + ... + F_4680607 is NOT divisible by 9797767 F_654321 + ... + F_987654 is divisible by 53 F_2468 + ... + F_897089 is NOT divisible by 87927879 F_654321 + ... + F_987654 is NOT divisible by 2809 F_654321 + ... + F_987654 is NOT divisible by 11881 F_780613 + ... + F_980156 is divisible by 6 F_654321 + ... + F_987654 is NOT divisible by 7647985 F_654321 + ... + F_987654 is divisible by 29717

Become really big Validator
Input
20 815 2064 37105079 815 2064 43851457 3189 789015 5242 3189 789015 15726 654317 987658 8 654317 987658 16 654317 987658 5 654317 987658 17 654317 987658 289 654317 987658 53 654317 987658 2809 654317 987658 109 654317 987658 11881 654317 987658 233 654317 987658 196925089 654317 987658 29717 654317 987658 883100089 654317 987658 37039 777666 905436 29186772 777666 905436 145933860
Output
F_815 + ... + F_2064 is divisible by 37105079 F_815 + ... + F_2064 is NOT divisible by 43851457 F_3189 + ... + F_789015 is divisible by 5242 F_3189 + ... + F_789015 is NOT divisible by 15726 F_654317 + ... + F_987658 is divisible by 8 F_654317 + ... + F_987658 is NOT divisible by 16 F_654317 + ... + F_987658 is NOT divisible by 5 F_654317 + ... + F_987658 is divisible by 17 F_654317 + ... + F_987658 is NOT divisible by 289 F_654317 + ... + F_987658 is divisible by 53 F_654317 + ... + F_987658 is NOT divisible by 2809 F_654317 + ... + F_987658 is divisible by 109 F_654317 + ... + F_987658 is NOT divisible by 11881 F_654317 + ... + F_987658 is divisible by 233 F_654317 + ... + F_987658 is NOT divisible by 196925089 F_654317 + ... + F_987658 is divisible by 29717 F_654317 + ... + F_987658 is NOT divisible by 883100089 F_654317 + ... + F_987658 is divisible by 37039 F_777666 + ... + F_905436 is divisible by 29186772 F_777666 + ... + F_905436 is NOT divisible by 145933860

Really huge Test
Input
13 987000000 987654321 6493915 123456789 123567900 8690943 523489014 528904156 121639 987000000 987654321 48533 987000000 987654321 3 987000000 987654321 2 523489014 528904156 364917 987000000 987654321 17 987000000 987654321 289 123456789 123567900 10373061 987000000 987654321 9349 987000000 987654321 34439 987000000 987654321 4021
Output
F_987000000 + ... + F_987654321 is NOT divisible by 6493915 F_123456789 + ... + F_123567900 is NOT divisible by 8690943 F_523489014 + ... + F_528904156 is divisible by 121639 F_987000000 + ... + F_987654321 is divisible by 48533 F_987000000 + ... + F_987654321 is NOT divisible by 3 F_987000000 + ... + F_987654321 is divisible by 2 F_523489014 + ... + F_528904156 is NOT divisible by 364917 F_987000000 + ... + F_987654321 is divisible by 17 F_987000000 + ... + F_987654321 is NOT divisible by 289 F_123456789 + ... + F_123567900 is divisible by 10373061 F_987000000 + ... + F_987654321 is divisible by 9349 F_987000000 + ... + F_987654321 is divisible by 34439 F_987000000 + ... + F_987654321 is divisible by 4021

Really huge Validator
Input
13 513489014 518904153 407935 513489014 518904153 482105 987123456 987654441 2 987123456 987654441 3 987123456 987654441 5 987123456 987654441 11 987123456 987654441 121 987123456 987654441 31 987123456 987654441 151 987123456 987654441 3001 987123456 987654441 12301 987123456 987654441 18451 987123456 987654441 987654441
Output
F_513489014 + ... + F_518904153 is divisible by 407935 F_513489014 + ... + F_518904153 is NOT divisible by 482105 F_987123456 + ... + F_987654441 is divisible by 2 F_987123456 + ... + F_987654441 is NOT divisible by 3 F_987123456 + ... + F_987654441 is divisible by 5 F_987123456 + ... + F_987654441 is divisible by 11 F_987123456 + ... + F_987654441 is NOT divisible by 121 F_987123456 + ... + F_987654441 is divisible by 31 F_987123456 + ... + F_987654441 is divisible by 151 F_987123456 + ... + F_987654441 is divisible by 3001 F_987123456 + ... + F_987654441 is divisible by 12301 F_987123456 + ... + F_987654441 is divisible by 18451 F_987123456 + ... + F_987654441 is NOT divisible by 987654441

Other really huge Test
Input
18 999000000 1000000000 15625 1000000000 1000000000 5 42 4894511 452240819 979000000 979002345 28883462 1000000000 1000000000 1953125 1000000000 1000000000 41 979000000 979002345 43325193 1000000000 1000000000 1681 999000000 1000000000 78125 1000000000 1000000000 3 999000000 1000000000 7 42 4894511 421051797 999000000 1000000000 11 1000000000 1000000000 9765625 1000000000 1000000000 1 999000000 1000000000 1681 1000000000 1000000000 7 1000000000 1000000000 11
Output
F_999000000 + ... + F_1000000000 is divisible by 15625 F_1000000000 + ... + F_1000000000 is divisible by 5 F_42 + ... + F_4894511 is divisible by 452240819 F_979000000 + ... + F_979002345 is divisible by 28883462 F_1000000000 + ... + F_1000000000 is divisible by 1953125 F_1000000000 + ... + F_1000000000 is divisible by 41 F_979000000 + ... + F_979002345 is NOT divisible by 43325193 F_1000000000 + ... + F_1000000000 is NOT divisible by 1681 F_999000000 + ... + F_1000000000 is NOT divisible by 78125 F_1000000000 + ... + F_1000000000 is divisible by 3 F_999000000 + ... + F_1000000000 is divisible by 7 F_42 + ... + F_4894511 is NOT divisible by 421051797 F_999000000 + ... + F_1000000000 is divisible by 11 F_1000000000 + ... + F_1000000000 is NOT divisible by 9765625 F_1000000000 + ... + F_1000000000 is divisible by 1 F_999000000 + ... + F_1000000000 is NOT divisible by 1681 F_1000000000 + ... + F_1000000000 is divisible by 7 F_1000000000 + ... + F_1000000000 is divisible by 11

Other really huge Validator
Input
18 666 1234561 15513751 666 1234561 18334433 978000000 978002345 10094978 978000000 978002345 35332423 998000000 1000000000 15625 998000000 1000000000 78125 998000000 1000000000 7 998000000 1000000000 11 998000000 1000000000 13 998000000 1000000000 41 998000000 1000000000 1681 1000000000 1000000000 1 1000000000 1000000000 3 1000000000 1000000000 5 1000000000 1000000000 1953125 1000000000 1000000000 9765625 1000000000 1000000000 7 1000000000 1000000000 11
Output
F_666 + ... + F_1234561 is divisible by 15513751 F_666 + ... + F_1234561 is NOT divisible by 18334433 F_978000000 + ... + F_978002345 is divisible by 10094978 F_978000000 + ... + F_978002345 is NOT divisible by 35332423 F_998000000 + ... + F_1000000000 is divisible by 15625 F_998000000 + ... + F_1000000000 is NOT divisible by 78125 F_998000000 + ... + F_1000000000 is divisible by 7 F_998000000 + ... + F_1000000000 is divisible by 11 F_998000000 + ... + F_1000000000 is divisible by 13 F_998000000 + ... + F_1000000000 is divisible by 41 F_998000000 + ... + F_1000000000 is NOT divisible by 1681 F_1000000000 + ... + F_1000000000 is divisible by 1 F_1000000000 + ... + F_1000000000 is divisible by 3 F_1000000000 + ... + F_1000000000 is divisible by 5 F_1000000000 + ... + F_1000000000 is divisible by 1953125 F_1000000000 + ... + F_1000000000 is NOT divisible by 9765625 F_1000000000 + ... + F_1000000000 is divisible by 7 F_1000000000 + ... + F_1000000000 is divisible by 11

Solution language

Solution

Stub generator input