### 11582 - Colossal Fibonacci Numbers!

Posted:

**Thu Feb 26, 2009 8:22 pm**I get Wrong answer

here is mycode :

here is mycode :

Code: Select all

```
Accepted
```

The Online Judge board

https://uva.onlinejudge.org/board/

https://uva.onlinejudge.org/board/viewtopic.php?f=50&t=42629

Page **1** of **1**

Posted: **Thu Feb 26, 2009 8:22 pm**

I get Wrong answer

here is mycode :

here is mycode :

Code: Select all

```
Accepted
```

Posted: **Thu Feb 26, 2009 10:14 pm**

Posted: **Fri Feb 27, 2009 8:16 am**

i got accepted by a lame method.

How did you find the period ? Found on net that period has to be less than 6*n. So generated upton 12*n and checked for repetition of first 10 numbers.

Anyone used floyd.

vahid, you are doing it wrong. a^b %n != a^b % p where p is the period, it could be within p<=6*n, source wikipedia

How did you find the period ? Found on net that period has to be less than 6*n. So generated upton 12*n and checked for repetition of first 10 numbers.

Anyone used floyd.

vahid, you are doing it wrong. a^b %n != a^b % p where p is the period, it could be within p<=6*n, source wikipedia

Posted: **Fri Feb 27, 2009 8:17 am**

thanks Jan but i dont have idea for solving that

could u give me some hints ?

could u give me some hints ?

Posted: **Fri Feb 27, 2009 8:19 am**

Thanks tryit , i try it

Posted: **Fri Feb 27, 2009 10:46 am**

It seems the the series returns back to 0 1 1 ... for every value of n.tryit1 wrote:i got accepted by a lame method.

How did you find the period ? Found on net that period has to be less than 6*n. So generated upton 12*n and checked for repetition of first 10 numbers.

Anyone used floyd.

I didn't know about the 6*n figure, so I just kept on inserting new values until a

Posted: **Fri Feb 27, 2009 12:44 pm**

Yes it returns backs to 0 1 1 .. But that observation can mislead. From your AC solution looks like it doesn't in this case.

If we are given a sequence of numbers like 0,1,1,2,3,5,6,7,0,1,1,2,0,1,1,2,3,5,6,7,0,1,1,2

how do you find the period of this ? Any thing easier than KMP.

If the values were unique could we apply floyd cycle finding. Can we modify it for the above sequence ? i tried but when there are duplicate values it breaks.

I guess there should be some algorithm which finds the period of a repeating sequence much easily.

If we are given a sequence of numbers like 0,1,1,2,3,5,6,7,0,1,1,2,0,1,1,2,3,5,6,7,0,1,1,2

how do you find the period of this ? Any thing easier than KMP.

If the values were unique could we apply floyd cycle finding. Can we modify it for the above sequence ? i tried but when there are duplicate values it breaks.

I guess there should be some algorithm which finds the period of a repeating sequence much easily.

Posted: **Fri Feb 27, 2009 12:58 pm**

I haven't understood fully. Its a Fibonacci sequence. So, you cant find a sequence that you have mentioned. However, suppose the sequence is based on any other criteria. Then stl map (or a bst) is a solution to your problem, too. Of course if the number of states is small.tryit1 wrote:Yes it returns backs to 0 1 1 .. But that observation can mislead. From your AC solution looks like it doesn't in this case.

If we are given a sequence of numbers like 0,1,1,2,3,5,6,7,0,1,1,2,0,1,1,2,3,5,6,7,0,1,1,2

how do you find the period of this ? Any thing easier than KMP.

If the values were unique could we apply floyd cycle finding. Can we modify it for the above sequence ? i tried but when there are duplicate values it breaks.

I guess there should be some algorithm which finds the period of a repeating sequence much easily.

Posted: **Fri Feb 27, 2009 1:35 pm**

You and sohel are right. It is a fibonacci sequence , so a first occurance of 0,1 starting with index > 2 solves the problem..My bad