10229  Modular Fibonacci
Moderator: Board moderators

 New poster
 Posts: 6
 Joined: Wed Jan 16, 2002 2:00 am
 Location: Ukraine
 Contact:
10229  Modular Fibonacci
There is my programm.
I cannot find where it fails.
// programm compute
// 1 1^(N1)
// 1 0
// with modular arithmetic
#include <iostream.h>
#include <math.h>
long N,L;
long double i,j,k,h,LL;
void mathpow(long N)
{ long t;
if (N>1)
{
mathpow(N/2);
//next 2 lines is M=M*M;
t=k*j;
k=i*k+k*h; j=i*j+j*h; i=i*i+t; h=h*h+t;
i=fmod(i,LL); j=fmod(j,LL); k=fmod(k,LL); h=fmod(h,LL);
}
if (N%2)
{
//next 2 lines is M=M*{{1,1},{1,0}}
t=i+j; j=i; i=t;
t=k+h; h=k; k=t;
i=fmod(i,LL); j=fmod(j,LL); k=fmod(k,LL); h=fmod(h,LL);
}
}
int ReadData()
{ long i;
cin>>N>>L;
for(i=1,LL=1;i<=L;i++,LL*=2);
return !cin.eof();
}
void Solve()
{
if(N==0) { cout<<0<<endl; return; }
i=1; j=0; k=0; h=1;
mathpow(N1);
cout<<i<<endl;
}
int main()
{
while(ReadData()) Solve();
return 0;
}
I cannot find where it fails.
// programm compute
// 1 1^(N1)
// 1 0
// with modular arithmetic
#include <iostream.h>
#include <math.h>
long N,L;
long double i,j,k,h,LL;
void mathpow(long N)
{ long t;
if (N>1)
{
mathpow(N/2);
//next 2 lines is M=M*M;
t=k*j;
k=i*k+k*h; j=i*j+j*h; i=i*i+t; h=h*h+t;
i=fmod(i,LL); j=fmod(j,LL); k=fmod(k,LL); h=fmod(h,LL);
}
if (N%2)
{
//next 2 lines is M=M*{{1,1},{1,0}}
t=i+j; j=i; i=t;
t=k+h; h=k; k=t;
i=fmod(i,LL); j=fmod(j,LL); k=fmod(k,LL); h=fmod(h,LL);
}
}
int ReadData()
{ long i;
cin>>N>>L;
for(i=1,LL=1;i<=L;i++,LL*=2);
return !cin.eof();
}
void Solve()
{
if(N==0) { cout<<0<<endl; return; }
i=1; j=0; k=0; h=1;
mathpow(N1);
cout<<i<<endl;
}
int main()
{
while(ReadData()) Solve();
return 0;
}
10229 (fibonacci modular)
why i got wa?
any tricky there?
i find the repetends for 0<=m<=20 and store them..
[cpp]
#include <stdio.h>
long data[3145727];
long a[21], sp[21];
int main()
{
long n, m, q;
long f1, f2, f3;
long len;
a[0] = 1; sp[0] = 0; data[0] = 0;
len = 1;
for (m = 1; m <= 20; m++) {
q = 1 << m;
sp[m] = len;
data[len++] = 0;
data[len++] = 1;
data[len++] = 1;
f1 = 1;
f2 = 1;
a[m] = 1;
while (f1 != 0  f2 != 1) {
a[m]++;
f3 = (f1 + f2) % q;
data[len++] = f3;
f1 = f2;
f2 = f3;
}
}
while (scanf("%ld %d", &n, &m) == 2) {
n %= a[m];
printf("%ld\n", data[sp[m] + n]);
}
return 0;
}
[/cpp]
any tricky there?
i find the repetends for 0<=m<=20 and store them..
[cpp]
#include <stdio.h>
long data[3145727];
long a[21], sp[21];
int main()
{
long n, m, q;
long f1, f2, f3;
long len;
a[0] = 1; sp[0] = 0; data[0] = 0;
len = 1;
for (m = 1; m <= 20; m++) {
q = 1 << m;
sp[m] = len;
data[len++] = 0;
data[len++] = 1;
data[len++] = 1;
f1 = 1;
f2 = 1;
a[m] = 1;
while (f1 != 0  f2 != 1) {
a[m]++;
f3 = (f1 + f2) % q;
data[len++] = f3;
f1 = f2;
f2 = f3;
}
}
while (scanf("%ld %d", &n, &m) == 2) {
n %= a[m];
printf("%ld\n", data[sp[m] + n]);
}
return 0;
}
[/cpp]
10229..............hints
am a novice programmer.i tried to solve this problem for many times,but failed. wud anyone plz give me some hints????
Well i tryed also do make this one but i've got a time limit exceeded, i tried the biggest case (2^31  1) and in my computer runned in 2s, what's the problem???
#include <stdio.h>
unsigned int m, n;
unsigned const int mascara[20] = {0, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767, 65535, 131071, 262143, 524287};
inline int fib() {
if (n == 0) {
return 0;
} else if (n == 1) {
return 1;
} else {
unsigned int fibA, fibB, fibTEMP;
fibA = 0;
fibB = 1;
for (register unsigned int i = 2 ; i <= n ; i++) {
fibTEMP = fibA + fibB;
fibA = fibB;
fibB = fibTEMP;
}
return fibB;
}
}
void processar() {
printf("%u\n", fib()&mascara[m]);
}
void main() {
while (scanf("%u%u", &n ,&m) == 2) {
processar();
}
}
#include <stdio.h>
unsigned int m, n;
unsigned const int mascara[20] = {0, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767, 65535, 131071, 262143, 524287};
inline int fib() {
if (n == 0) {
return 0;
} else if (n == 1) {
return 1;
} else {
unsigned int fibA, fibB, fibTEMP;
fibA = 0;
fibB = 1;
for (register unsigned int i = 2 ; i <= n ; i++) {
fibTEMP = fibA + fibB;
fibA = fibB;
fibB = fibTEMP;
}
return fibB;
}
}
void processar() {
printf("%u\n", fib()&mascara[m]);
}
void main() {
while (scanf("%u%u", &n ,&m) == 2) {
processar();
}
}
Best regards,
S
S
Well i tryed also do make this one but i've got a time limit exceeded, i tried the biggest case (2^31  1) and in my computer runned in 2s, what's the problem???
Maybe this is more clear than the above...
[cpp]
#include <stdio.h>
unsigned int m, n;
unsigned const int mascara[20] = {0, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767, 65535, 131071, 262143, 524287};
inline int fib() {
if (n == 0) {
return 0;
} else if (n == 1) {
return 1;
} else {
unsigned fibA, fibB, fibTEMP;
fibA = 0;
fibB = 1;
for (register unsigned int i = 2 ; i <= n ; i++) {
fibTEMP = fibA + fibB;
fibA = fibB;
fibB = fibTEMP;
}
return fibB;
}
}
void processar() {
printf("%u\n", fib()&mascara[m]);
}
void main() {
while (scanf("%u%u", &n ,&m) == 2) {
processar();
}
}[/cpp]
Maybe this is more clear than the above...
[cpp]
#include <stdio.h>
unsigned int m, n;
unsigned const int mascara[20] = {0, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767, 65535, 131071, 262143, 524287};
inline int fib() {
if (n == 0) {
return 0;
} else if (n == 1) {
return 1;
} else {
unsigned fibA, fibB, fibTEMP;
fibA = 0;
fibB = 1;
for (register unsigned int i = 2 ; i <= n ; i++) {
fibTEMP = fibA + fibB;
fibA = fibB;
fibB = fibTEMP;
}
return fibB;
}
}
void processar() {
printf("%u\n", fib()&mascara[m]);
}
void main() {
while (scanf("%u%u", &n ,&m) == 2) {
processar();
}
}[/cpp]
Best regards,
S
S
Look don't say that is obviously going to be TLE, my algorithm runs at O(n), as the maximum input is 2^31 1 so the max running time is:
T = (2^311) /(10^9) ~ 2 so its 2 seconds aproximately.
Talking about algorithms i only know calculating fibonacci with the obscure formula
Fn = 1/sqrt(5)*[ 1/2*(1+sqrt(5)^n  1/2*(1sqrt(5)^n)];
but i thing its inapropriate...
another way i thought was making preprocessing of some values ex:
storing fibonnaci of 100,101,1000,1001,10000,10001, ... something like this... and using for saving time, e.g. if i wanted to calculate the fibonacci of 1010 i was going to start to calculate in 1000...
T = (2^311) /(10^9) ~ 2 so its 2 seconds aproximately.
Talking about algorithms i only know calculating fibonacci with the obscure formula
Fn = 1/sqrt(5)*[ 1/2*(1+sqrt(5)^n  1/2*(1sqrt(5)^n)];
but i thing its inapropriate...
another way i thought was making preprocessing of some values ex:
storing fibonnaci of 100,101,1000,1001,10000,10001, ... something like this... and using for saving time, e.g. if i wanted to calculate the fibonacci of 1010 i was going to start to calculate in 1000...
Best regards,
S
S
i've found an algorithm that runs in O(log(n)) and i've got an AC for anyone who is curious go to
http://www.ics.uci.edu/~dan/class/161/notes/7/Fib.html
it ran in 0.02 s
http://www.ics.uci.edu/~dan/class/161/notes/7/Fib.html
it ran in 0.02 s
Best regards,
S
S