FSEQ - No Stories Any More!

no tags 

Have you ever wished to be given a direct problem statement in the contest? Do you hate the boring stories that problem setters write...starting from “john was going on a trip”…passing with “blablabla”…and ending with “kindly help John J”. We all know that there is no John so why wasting contestants time. As we were contestants and know that feeling very well, we decided to break that boring way and save your time…

Given the following sequence details:  F(0) = 0, F(1) = 1       and 

           SUM F(i) [i from 0 to n] = F(n+2) - 1

For a given integer M, we will generate another infinite sequence defined as:  T(i) = F(i) % M. We noticed that this is a repeating sequence: it repeats itself after some C iterations, where C is the cycle length for sequence T. Let’s define H(j), as the finite, most left, strictly increasing sub-sequence starting at position j in the sequence T, preserving the elements order of T. In other words:

1)      H(0), the first element in H, is T(j)

2)      H(1)  = T(k1), where T(k1) is the first element > T(j) where j < k1

3)      H(2)  = T(k2), where T(k2) is the first element > T(k1) where k1 < k2, and so on

For example, if M = 4, then T = [0 1 1 2 3 1   0 1 1 2 3 1   0 1 1 2 …]. Furthermore: H(0) = [0 1 2 3], H(3) = [2 3], and H(5) = [1 2 3]. Length(  H(j) ) is the number of elements in that sequence, e.g. Length(H(5)) = 3. The Cycle length(C) for sequence T is 6.

 

For a given M, you will calculate its C, and evaluate the following summation:

                                          SUM Length( H(k) ) [k = 0 to C-1]

Input Specification:

The first line of input contains an integer T that represents the number of test cases, then follow T lines each contains an integer 1 ≤ M ≤ 105. NOTE: for any given test case, sequence T repeats after maximum C iterations where C ≤ 105.

Output Specification:

For each test case, output a single line of output in the form “Case K: summation” where K is the number of the test case and summation is as defined in the problem statement.

 

Sample input:

1

4

Sample Output:

Case 1: 16


hide comments
Abhishek Goel: 2012-06-27 08:49:43

fially accepted
1
1000
Case 1: 12292

Last edit: 2012-06-27 15:52:19
suhang: 2012-04-18 00:57:17

Thanks,i got AC with your help

shihanyuan: 2012-04-17 13:47:59

I think the ans is 1993109.

Last edit: 2012-04-18 00:44:48
suhang: 2012-04-05 00:49:48

M=100000,result is 4922128125?

Luke Pebody: 2011-11-16 07:44:04

(I think this might have been deliberately self-aware by the problem setter)


Added by:Mostafa Saad Ibrahim
Date:2011-11-13
Time limit:1.489s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:10th Egyptian Collegiate Programming Contest