Header Ad

HackerEarth Special series problem solution

In this HackerEarth Special series problem solution Consider a series F that is defined as follows:
  1. F(1) = 1
  2. F(2) = 1
  3. F(3) = 2
  4. For n >= 3, F(n*n) - F(n + 1) x F(n -1) = ((-1) to power n)
Given two integers n and m. We need to make the nth term and mth term of the series co-prime. Find the largest positive number by which we must divide the nth term and mth term of the series such both terms become co-prime. Since, this number can be very large, print it modulo 10 to power 9 plus 7.


HackerEarth Special series problem solution


HackerEarth Special series problem solution.

#include <bits/stdc++.h>
#define ll long long int
#define sc1(x) scanf("%d",&x)
#define sc2(x,y) scanf("%d%d",&x,&y)
#define scll(x) scanf("%lld",&x)
#define pint(c) printf("%d",c)
#define pll(c) printf("%lld",c)
#define ps() printf(" ")
#define pn() printf("\n")

#define vi vector<int>
#define vii vector<pair<int,int> >
#define mp make_pair
#define pb push_back
#define ff(i,n,a) for(i=a;i<n;++i)
#define fb(i,n,a) for(i=n,i>=a;--i)
const int mxn=1e5+1;
const int M=1e9+7;
using namespace std;

void matmult(long long a[][2], long long b[][2],long long c[][2])
{
int i,j,k;
for(i=0;i<2;i++)
{
for(j=0;j<2;j++)
{
c[i][j]=0;
for(k=0;k<2;k++)
{
c[i][j]+=(a[i][k]*b[k][j])%M;
c[i][j]=c[i][j]%M;
}
}
}

}
void matpow(long long Z[][2],int n,long long ans[][2])
{

long long temp[2][2];
ans[0][0]=1;
ans[1][0]=0;
ans[0][1]=0;
ans[1][1]=1;
int i,j;
while(n>0)
{
if(n&1)
{
matmult(ans,Z,temp);
for(i=0;i<2;i++)
for(j=0;j<2;j++)
ans[i][j]=temp[i][j];
}
matmult(Z,Z,temp);
for(i=0;i<2;i++)
for(j=0;j<2;j++)
Z[i][j]=temp[i][j];


n=n/2;
}
return;

}

long long findFibonacci(long long n)
{

long long fib;
if(n>2)
{
long long int Z[2][2]={{1,1},{1,0}},result[2][2];
matpow(Z,n-2,result);
fib=result[0][0]*1 + result[0][1]*0;
}
else
fib=n-1;

return fib;
}

ll getGcd(string s,ll n)
{
ll b=0;
for(int i=0;i<s.length();++i)
b=(b*10+(s[i]-48))%n;
return __gcd(n,b);
}

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
assert(1 <= t and t <= 100);
while(t--)
{

string s;
long long n;
cin>>s;
assert(s.size() <= 100000 and s.size() >= 1);
cin>>n;
assert(1 <= n and n <= 1000000000);
ll gc=getGcd(s,n);
cout<<findFibonacci(gc+1)<<"\n";
}
return 0;
}

Second solution

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int MAX_N = 1e4 + 14, MOD = 1e9 + 7;


struct Mat {
static constexpr int MAX_MAT = 2;
int a[MAX_MAT][MAX_MAT];

explicit Mat(bool emp = false) {
memset(a, 0, sizeof a);
if (emp)
for (int i = 0; i < MAX_MAT; i++)
a[i][i] = 1;
}

const int *operator[](int i) const {
return a[i];
}

int *operator[](int i) {
return a[i];
}

Mat operator+(const Mat &b) {
Mat ret;
for (int i = 0; i < MAX_MAT; i++)
for (int j = 0; j < MAX_MAT; j++)
ret[i][j] = a[i][j] + b[i][j];
return ret;
}

Mat operator*(const Mat &b) {
Mat ret;
for (int k = 0; k < MAX_MAT; k++)
for (int i = 0; i < MAX_MAT; i++)
for (int j = 0; j < MAX_MAT; j++)
ret[i][j] = (ret[i][j] + (ll) a[i][k] * b[k][j]) % MOD;
return ret;
}

Mat operator^(int b) {
Mat a = *this;
Mat ret(true);
for (; b; b >>= 1, a = a * a)
if (b & 1)
ret = ret * a;
return ret;
}
};

int main() {
ios::sync_with_stdio(0), cin.tie(0);
Mat base_fib;
base_fib[0][0] = base_fib[0][1] = base_fib[1][0] = 1;
int t;
cin >> t;
while (t--) {
string n;
int m;
cin >> n >> m;
int g = 0;
for (auto c : n)
g = (g * 10ll + c - '0') % m;
g = gcd(g, m);
cout << (base_fib ^ g)[0][1] << '\n';
}
}


Post a Comment

0 Comments