PROBLEM LINKS :
Contest : Division 1
Contest : Division 2
Practice
Setter : Kevin Matthew T
Tester : Istvan Nagy
Editorialist : Anand Jaisingh
DIFFICULTY :
Easy
PREREQUISITES :
Properties of Fibonacci Numbers, Bit Manipulation
PROBLEM :
After some deductions from a long statement, the problem is : Given a number N, we need to find the (X-1)^{th} Fibonacci number modulo 10, where X is 2^{MSB(N)}. Here, MSB(N) denotes the most significant bit of the number N.
QUICK EXPLANATION :
We can prove that for any sequence D_1,D_2,...,D_N which follows the nature given in the problem statement, the number remaining in the end is the number 2^{MSB(N)} where MSB(N) denotes the most significant bit of the number N. Additionally, we deduce that we need to calculate f(2^{MSB(N)} -1) \mod 10 , as the last digit of a number x is same as the number x \mod 10 . Finally, we shall use the property that the fibonacci numbers are periodic Modulo any given number.
EXPLANATION :
Terminology :
MSB(N) : It denotes the highest X, such that in the binary representation of the number N , the X^{th} bit is 1.
LSB(N) : It denotes the smallest X, such that in the binary representation of the number N , the X^{th} bit is 1.
Now, before moving to Fibonacci Numbers, let’s just first try and understand the behavior of the sequence D_1,D_2,....,D_N
Claim :
After i \ge 1 moves have been conducted over the sequence D, then the only numbers remaining are ones having their LSB \ge i
Proof :
In the first move, we exactly destroy all odd numbers, i.e. all numbers X, such that LSB(X)=0. In the second move, we destroy all numbers X, such that LSB(X)=1. As we go on, we can see that the only numbers remaining after the i^{th} move are the ones having LSB \ge i
Moving on,
Now, to reduce a sequence of N numbers D_1,D_2,...D_N to a sequence of size 1, it takes exactly \left\lfloor{\log_2{N}}\right\rfloor steps. But its quite simple to see that the number N is represented using \left\lfloor{\log_2{N}}\right\rfloor +1 bits.
So, after we’ve performed \left\lfloor{\log_2{N}}\right\rfloor steps, the size of the list should be 1, and we should have removed all numbers X, such that LSB(X) < \left\lfloor{\log_2{N}}\right\rfloor . Indeed, only 1 number \ge 1 and \le N satisfies the condition that its LSB \ge \left\lfloor{\log_2{N}}\right\rfloor , and that is the number 2^{MSB(N)}.
Now, moving to Fibonacci Numbers,
For any number X, its last digit is given by X \mod 10 . So, instead of considering that we are generating the sequence using the last digit and so on, in fact we can consider we just calculate the Fibonacci Numbers Modulo 10.
This gives us the the recurrence
f(0)=0,f(1)=1
f(i) = (f(i-1)+f(i-2)) \mod 10 , \hspace{0.2cm} i \ge 2
And since D_i = f(i-1) for i \ge 1 , we need to calculate f(2^{MSB(N)}-1) . Now to proceed further, we need to use a well known fact, which states that the Fibonacci Numbers are Periodic Modulo any given number, and in the case of the number 10, the period is 60.
This gives us, \forall \hspace{0.1cm} i \ge 60, f(i)=f(i-60), which in turn gives us :
f(i) = f(i \mod 60)
So, we can calculate the first 60 Fibonacci Numbers, everything Modulo 10, and then just print f((2^{MSB(N)}-1) \mod 60 ) .
That’s it, Thank you !
Your Comments are Welcome !
COMPLEXITY ANALYSIS :
Time Complexity : O(T \cdot \log(N) + Z) , where Z \approx 60
Space Complexity : O(Z), where Z \approx 60
SOLUTION LINKS :
Setter
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ld;
// Kevin Mathew T
// Birla Institute of Technology, Mesra
// GitHub - https://github.com/KevinMathewT
// CodeForces - https://codeforces.com/profile/KevinMathew
// CodeChef - https://www.codechef.com/users/KevinMathew
// HackerRank - https://www.hackerrank.com/KevinMathew
// LinkedIn - https://www.linkedin.com/in/KevinMathewT
ll n, fib[100];
int main()
{
// freopen("input.txt", "r", stdin); //Comment
// freopen("output.txt", "w", stdout); //this out.
ios::sync_with_stdio(false); //Not
cin.tie(NULL); //this.
cout.tie(0); //or this.
fib[0] = 0;
fib[1] = 1;
for(ll i=2;i<60;i++)
fib[i] = fib[i-1] + fib[i-2];
for(ll i=0;i<60;i++){
fib[i] = fib[i] % 10;
}
ll T;
cin >> T;
while(T--){
cin >> n;
// ll t = n;
// cin >> n;
// n = (((ll) pow(2, (ll)log2(n))) - 1) % 60;
ll pos = 0;
while (n >>= 1) ++pos;
// cout << pos << "--\n";
n = ((ll) pow(2, pos) - 1) % 60;
cout << fib[n] << "\n";
}
return 0;
}
Tester
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
template<class T> bool umin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool umax(T &a, T b) { return a < b ? (a = b, true) : false; }
using namespace std;
int main(int argc, char** argv)
{
#ifdef HOME
if (IsDebuggerPresent())
{
freopen("../in.txt", "rb", stdin);
freopen("../out.txt", "wb", stdout);
}
#endif
vector<int> fb(1050);
int loopstart = 0, loopend = 0;
fb[1] = 1;
for (int i = 2; i < fb.size(); ++i)
{
fb[i] = (fb[i - 1] + fb[i - 2]) % 10;
for (int j = 1; j < i; ++j)
{
if (fb[i] == fb[j] && fb[i - 1] == fb[j - 1])
{
loopend = i;
loopstart = j;
break;
}
}
if (loopend)
break;
}
int T;
int64_t N, pw;
scanf("%d", &T);
for (int tc = 0; tc < T; ++tc)
{
scanf("%lld", &N);
pw = 1;
while (2 * pw <= N)
{
pw *= 2;
}
pw--;
pw %= (loopend - loopstart);
printf("%d\n", fb[pw]);
}
return 0;
}
Editorialist
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
//#pragma GCC target("avx,tune=native")
// Anand Jaisingh
#include<bits/stdc++.h>
using namespace std;
typedef complex<double> base;
typedef long double ld;
typedef long long ll;
#define pb push_back
#define pii pair<int,int>
#define pll pair< ll , ll >
#define vi vector<int>
#define vvi vector< vi >
const int maxn=(int)(2e5+5);
const ll mod=(ll)(1e9+7);
int a[maxn];
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
int t;cin>>t;
while(t>0)
{
ll n;cin>>n;int high=-1;
for(ll i=0;i<62;i++)
{
ll now=1ll<<i;
if((n&now)!=0)
{
high=i;
}
}
vector<int> v;v.resize(60);v[1]=1;
for(int i=2;i<60;i++)
{
int now=(v[i-1]+v[i-2])%10;
v[i]=now;
}
int zz=(1ll<<high)%60ll;
cout<<v[zz-1]<<endl;
t--;
}
return 0;
}
had spent hours on it trying to debug it during the contest but to no good .
