## 10229 - Modular Fibonacci

**Moderator:** Board moderators

### 10229 :WA.....I am angry now !!!

Hi !! here is my code , I am getting wrong answer ..can anybody help me.......

what is wrong ??

#include<iostream>

#include<cstdio>

#include<math.h>

using namespace std;

long long int Fib(long long int n)

{

long long int i=1,h=1;

long long int j =0,k=0,t;

while (n > 0) {

if (n%2 == 1) {

t = j*h;

j = i*h + j*k + t;

i = i*k + t;

}

t = h*h;

h = 2*k*h + t;

k = k*k + t;

n=(int)floor(n/2.0);

}

return j;

}

int main()

{

long long int n,m;

while(scanf("%lld%lld",&n,&m)!=EOF)

{

printf("%lld\n",Fib(n)%((int)pow(2,m)));

}

return 0;

}

even this algo is work on O(lon(n));;;;.....reaply.. soon

thanks..

what is wrong ??

#include<iostream>

#include<cstdio>

#include<math.h>

using namespace std;

long long int Fib(long long int n)

{

long long int i=1,h=1;

long long int j =0,k=0,t;

while (n > 0) {

if (n%2 == 1) {

t = j*h;

j = i*h + j*k + t;

i = i*k + t;

}

t = h*h;

h = 2*k*h + t;

k = k*k + t;

n=(int)floor(n/2.0);

}

return j;

}

int main()

{

long long int n,m;

while(scanf("%lld%lld",&n,&m)!=EOF)

{

printf("%lld\n",Fib(n)%((int)pow(2,m)));

}

return 0;

}

even this algo is work on O(lon(n));;;;.....reaply.. soon

thanks..

Programming...

I got WA.....

plz give me some input/ output.....

here is my code:

plz give me some input/ output.....

here is my code:

Code: Select all

`remove after ACC`

**plz help..........**
Last edited by joy on Fri Dec 22, 2006 7:15 pm, edited 1 time in total.

form kisui na ... class tai asol....

iF U hv d class u get the form....

iF U hv d class u get the form....

Check the samples...

Hope these help.

**Input:**Code: Select all

```
288 6
15006 1
22929 1
4596 1
```

**Output:**Code: Select all

```
0
0
0
0
```

Ami ekhono shopno dekhi...

HomePage

HomePage

thanks Jane ...

I got ACC now

I got ACC now

Last edited by joy on Fri Jan 26, 2007 1:47 pm, edited 1 time in total.

form kisui na ... class tai asol....

iF U hv d class u get the form....

iF U hv d class u get the form....

Hi

Could anyone tell me how to solve tihs problem ?

I've got our Fn by using O(lg) algorithm and I know that

(a*b*c)%n==((a%n)*(b%n)*(c%n))%n

but I don't know how to use it?

Should I find prime factors of this number and use them to calculate Fn%m - I think that 2147483647th fibbonacii is too big for doing this .

I'm confused.

plx help me

jojo

Could anyone tell me how to solve tihs problem ?

I've got our Fn by using O(lg) algorithm and I know that

(a*b*c)%n==((a%n)*(b%n)*(c%n))%n

but I don't know how to use it?

Should I find prime factors of this number and use them to calculate Fn%m - I think that 2147483647th fibbonacii is too big for doing this .

I'm confused.

plx help me

jojo

"Don't let the system get you down!"

hi,jojo wrote:Hi

Could anyone tell me how to solve tihs problem ?

I've got our Fn by using O(lg) algorithm and I know that

(a*b*c)%n==((a%n)*(b%n)*(c%n))%n

but I don't know how to use it?

Should I find prime factors of this number and use them to calculate Fn%m - I think that 2147483647th fibbonacii is too big for doing this .

I'm confused.

plx help me

jojo

Code: Select all

```
Sequence of Fibonacci numbers:
Fibo(i) : 1 1 2 3 5 8 13 21 34 55 89 144 233...
Sequence of Fibonacci numbers mod 2:
Fibo(i)%2 : 1 1 0 1 1 0 1 1 0...
Sequence of Fibonacci numbers mod 3:
Fibo(i)%3 : 1 1 2 0 2 2 1 0 1 1 2 0...
```

Hope it helps..

form kisui na ... class tai asol....

iF U hv d class u get the form....

iF U hv d class u get the form....

### 10229 runtime error

I have runtime error, but I don't know why? Somebody can tell me what's wrong with this code? :

Code: Select all

```
#include<iostream>
using namespace std;
int fibon(int a);
int potega(int b);
int main()
{
int n, m;
while(cin>>n>>m)
{ cout<<fibon(n)%potega(m)<<"\n"; }
}
/*****************************************************/
int fibon(int a)
{
if(a==0) return 0;
if(a<1) return 1;
else
return (fibon(a-1)+ fibon(a-2));
}
int potega(int b)
{
int pomoc=1;
for(int i=0; i<b; i++)
{ pomoc*=2; }
return pomoc;
}
```

wyvmak wrote:at a rough scan on your code, what i think is, there seems not a need to use long double, you can make it to int, or long long. then, your program may be better, at least need not worry about floating point error. though i cannot tell you whether it will get AC

### Re: 10229 - Modular Fibonacci

can somebody please point out why am i getting WA?

Code: Select all

```
#include<iostream>
using namespace std;
long long p;
long long pow(int i,int j)
{
long long val=1;
int k;
for (k=1;k<=j;k++)
val=val*i;
return val;
}
long long conquer_fibonacci(long long n)
{
long long i,h,j,k,t;
i=h=1;
j=k=0;
while(n>0)
{
if(n%2==1)
{
t=j*h;
j=((i*h)%p + (j*k)%p +t%p)%p;
i=i*k + t;
}
t=h*h;
h=2*k*h + t;
k=k*k + t;
n=(long long) n/2;
}
return j;
}
int main()
{
long long n,res,m;
while(scanf("%lld%lld",&n,&m)!=EOF)
{
p=pow(2,m);
res=conquer_fibonacci(n);
printf("%lld\n",res%pow(2,m));
}
return 0;
}
```

### Re: 10229 - Modular Fibonacci

Sometimes k and t can be very big.. so it may cause overflow error..fR0D wrote:can somebody please point out why am i getting WA?

### 10229 - Modular Fibonacci --> here more case testing

**Input**

11 7

11 6

2147483647 2

0 0

2147483647 0

2147483647 19

**output**

89

25

1

0

0

325917