C++
Fibonacci Sequence The well-known Fibonacci sequence is: Fi Fi Fi-2 fori 2 2, Fo 0. F1-1 Tom discovers that the Fibonacci number grows very quickly, for example F40 - 102334155. To make further discovery of the Fibonacci numbers, Tom takes the following steps 1. Take the first n Fibonacci numbers (exclude Fo) S1-(F1. F2. Fn) 2. Modulo each Fibonacci number by a positive integer Q.e. Ai-Fi % Q and obtain a new sequence S2-(A1. A2. Sort the numbers in S2 from small to large and obtain sequence S3 S2-(A1, A2. ..., An) -S3-ci. c2...., cn J For numbers in sequence S3, calculate the weighted sum modular Q An J 3. 4. Can you write a program to calculate the result? Input The input contains multiple test cases. The first line of the input is a number T (1 sTs100). indicating the number of test cases. Each test case contains two integers n (2 S ns 5,000,000) and Q (2 sQ 1000,000,000) in one line Output For each test case, print the weighted sum in a separate line Sample input 4 5 100 Sample output 46 15 13 5000000 1000000000 973061125 Explanation: In the second sample: the first 5 Fibonacci numbers are {1. 1. 2. 3. 5}, after modular 3 it becomes {1. 1, 2, 0, 2) and after sorting it is (0.1.1.2.2). hence the weighted sum is 0.11 2+1 3+2-4+2 5 23 After modular 3 it is 23 % 3 2 Hints: radix sort Fibonacci Sequence The well-known Fibonacci sequence is: Fi Fi Fi-2 fori 2 2, Fo 0. F1-1 Tom discovers that the Fibonacci number grows very quickly, for example F40 - 102334155. To make further discovery of the Fibonacci numbers, Tom takes the following steps 1. Take the first n Fibonacci numbers (exclude Fo) S1-(F1. F2. Fn) 2. Modulo each Fibonacci number by a positive integer Q.e. Ai-Fi % Q and obtain a new sequence S2-(A1. A2. Sort the numbers in S2 from small to large and obtain sequence S3 S2-(A1, A2. ..., An) -S3-ci. c2...., cn J For numbers in sequence S3, calculate the weighted sum modular Q An J 3. 4. Can you write a program to calculate the result? Input The input contains multiple test cases. The first line of the input is a number T (1 sTs100). indicating the number of test cases. Each test case contains two integers n (2 S ns 5,000,000) and Q (2 sQ 1000,000,000) in one line Output For each test case, print the weighted sum in a separate line Sample input 4 5 100 Sample output 46 15 13 5000000 1000000000 973061125 Explanation: In the second sample: the first 5 Fibonacci numbers are {1. 1. 2. 3. 5}, after modular 3 it becomes {1. 1, 2, 0, 2) and after sorting it is (0.1.1.2.2). hence the weighted sum is 0.11 2+1 3+2-4+2 5 23 After modular 3 it is 23 % 3 2 Hints: radix sort
