[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/functions.php on line 4756: Cannot modify header information - headers already sent by (output started at [ROOT]/includes/functions.php:3891)
[phpBB Debug] PHP Warning: in file [ROOT]/includes/functions.php on line 4758: Cannot modify header information - headers already sent by (output started at [ROOT]/includes/functions.php:3891)
[phpBB Debug] PHP Warning: in file [ROOT]/includes/functions.php on line 4759: Cannot modify header information - headers already sent by (output started at [ROOT]/includes/functions.php:3891)
[phpBB Debug] PHP Warning: in file [ROOT]/includes/functions.php on line 4760: Cannot modify header information - headers already sent by (output started at [ROOT]/includes/functions.php:3891)
Dev Skill Forum • View topic - WHY WA DCP-138: The Last Fibonacci

WHY WA DCP-138: The Last Fibonacci

Dev Skill archived problems can be discussed here.

WHY WA DCP-138: The Last Fibonacci

by joy25896 » Fri Jan 20, 2017 5:32 pm

#include <iostream>
#include<bits/stdc++.h>
#define LL long long int
using namespace std;

long long fibonacci(long long int n)
{
long long fib[2][2]= {{1,1},{1,0}},ret[2][2]= {{1,0},{0,1}},tmp[2][2]= {{0,0},{0,0}};
int i,j,k;
while(n)
{
if(n&1)
{
memset(tmp,0,sizeof tmp);
for(i=0; i<2; i++) for(j=0; j<2; j++) for(k=0; k<2; k++)
tmp[i][j]=(tmp[i][j]+ret[i][k]*fib[k][j]);
for(i=0; i<2; i++) for(j=0; j<2; j++) ret[i][j]=tmp[i][j];
}
memset(tmp,0,sizeof tmp);
for(i=0; i<2; i++) for(j=0; j<2; j++) for(k=0; k<2; k++)
tmp[i][j]=(tmp[i][j]+fib[i][k]*fib[k][j]);
for(i=0; i<2; i++) for(j=0; j<2; j++) fib[i][j]=tmp[i][j];
n/=2;
}
return (ret[0][1]);
}

int main ()
{
int t,i=1;
cin>>t;
while(t--)
{
LL n;
cin>>n;
LL ss=fibonacci(n);
//cout<<"============"<<ss<<"=========="<<endl;
LL num=ss%10;
cout<<"Case "<<i<<": "<<num<<" is the last digit."<<endl;

i++;
}

return 0;
}
 
Posts: 30
Joined: Wed Nov 16, 2016 3:29 pm
Location: dhaka bangladesh

Re: WHY WA DCP-138: The Last Fibonacci

by mahrahat » Fri Jan 20, 2017 11:20 pm

92nd Fibonacci number is 7540113804746346429 which is the largest Fibonacci number that can be assigned to a long long int. Using unsigned long long, it is possible to calculate upto 93rd Fibonacci number (12200160415121876738). The next number in the series is too large to 'fit' even in a unsigned long long variable. This is why your code will produce incorrect output when N is greater than 92.
 
Posts: 48
Joined: Thu Nov 24, 2016 9:11 pm
Location: Bangladesh

Re: WHY WA DCP-138: The Last Fibonacci

by mahrahat » Tue Jan 24, 2017 12:14 am

To solve this problem you need to utilize the fact that the last digit of a Fibonacci number repeats with a periodicity of 60.
 
Posts: 48
Joined: Thu Nov 24, 2016 9:11 pm
Location: Bangladesh

Re: WHY WA DCP-138: The Last Fibonacci

by joy25896 » Sun Feb 05, 2017 11:00 pm

DONE........
 
Posts: 30
Joined: Wed Nov 16, 2016 3:29 pm
Location: dhaka bangladesh

Re: WHY WA DCP-138: The Last Fibonacci

by mahrahat » Mon Feb 06, 2017 1:43 am

:) :)
 
Posts: 48
Joined: Thu Nov 24, 2016 9:11 pm
Location: Bangladesh


Who is online
Users browsing this forum: Google [Bot] and 1 guest
cron