10229 - Modular Fibonacci

All about problems in Volume 102. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

akdwivedi
New poster
Posts: 2
Joined: Mon Jun 26, 2006 8:17 am

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

Post by akdwivedi » Fri Jun 30, 2006 8:15 pm

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..
Programming...

898989
Learning poster
Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt
Contact:

Post by 898989 » Fri Jun 30, 2006 8:37 pm

Salamo Aleko
You can visit steven halim site for uva problem solving
And find the implemenation in his explantation
I used it and get ac in 10 minutes.
Sorry i do not know a reference. If you got a link..give it to us.
Sleep enough after death, it is the time to work.
Mostafa Saad

joy
New poster
Posts: 48
Joined: Wed Oct 18, 2006 1:00 pm
Location: Dhaka, Bangladesh
Contact:

Post by joy » Tue Dec 05, 2006 11:48 am

I got WA.....
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....

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sat Dec 09, 2006 7:50 am

Check the samples...

Input:

Code: Select all

288 6
15006 1
22929 1
4596 1
Output:

Code: Select all

0
0
0
0
Hope these help.
Ami ekhono shopno dekhi...
HomePage

joy
New poster
Posts: 48
Joined: Wed Oct 18, 2006 1:00 pm
Location: Dhaka, Bangladesh
Contact:

Post by joy » Fri Dec 22, 2006 7:14 pm

thanks Jane :D ...

I got ACC now :D
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....

jojo
New poster
Posts: 2
Joined: Mon Jul 24, 2006 2:36 pm
Location: Poland

Post by jojo » Fri Jan 26, 2007 12:17 am

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
"Don't let the system get you down!"

joy
New poster
Posts: 48
Joined: Wed Oct 18, 2006 1:00 pm
Location: Dhaka, Bangladesh
Contact:

Post by joy » Fri Jan 26, 2007 2:26 pm

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
hi,

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...
You dont need to use n time loop to solve this problem

Hope it helps..
form kisui na ... class tai asol....
iF U hv d class u get the form....

code_man
New poster
Posts: 4
Joined: Tue Jan 16, 2007 6:07 pm

10229 runtime error

Post by code_man » Wed May 16, 2007 6:13 pm

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;     
}

User avatar
newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Location: Campus Area. Dhaka.Bangladesh
Contact:

Post by newton » Sun Jul 22, 2007 12:55 pm

i cant find the point like jojo.
may you help explaining it elaborately....



thanx
Last edited by newton on Sun Jul 22, 2007 1:30 pm, edited 1 time in total.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Sun Jul 22, 2007 1:05 pm

Read previous posts in this thread.

ifox
New poster
Posts: 1
Joined: Sat Sep 08, 2007 4:56 am

Post by ifox » Sat Sep 08, 2007 5:00 am

yes, long long will get ac

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

fR0D
New poster
Posts: 29
Joined: Mon Feb 11, 2008 5:59 am
Contact:

Re: 10229 - Modular Fibonacci

Post by fR0D » Sat May 31, 2008 4:09 pm

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;
}

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Re: 10229 - Modular Fibonacci

Post by helloneo » Sat May 31, 2008 4:43 pm

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

fR0D
New poster
Posts: 29
Joined: Mon Feb 11, 2008 5:59 am
Contact:

Re: 10229 - Modular Fibonacci

Post by fR0D » Sat May 31, 2008 9:08 pm

so how can i avoid that???

carliros
New poster
Posts: 6
Joined: Wed Aug 13, 2008 1:30 am

10229 - Modular Fibonacci --> here more case testing

Post by carliros » Wed Aug 13, 2008 1:36 am

Input
11 7
11 6
2147483647 2
0 0
2147483647 0
2147483647 19

output
89
25
1
0
0
325917

Post Reply

Return to “Volume 102 (10200-10299)”