304 North Cardinal St.
Dorchester Center, MA 02124

# Stepping Numbers CodeChef Solution

## Stepping Numbers CodeChef Solution in C++17

``````
#include <stdio.h>
#include <stdlib.h>

#define ullint unsigned long long
#define uint unsigned int

#define MOD 4294967143ULL
#define MODINV 1789569643ULL

typedef struct {
ullint a;
ullint b;
} surd;

inline ullint modprod(ullint a, ullint b) {
return (a*b) % MOD;
}

inline ullint modminus(ullint a, ullint b) {
a = a % MOD;
b = b % MOD;
if (a >= b)
return a - b;
else
return (MOD - b) + a;
}

inline surd mult(surd s1, surd s2) {
surd res;
res.a = (modprod(s1.a,s2.a) + modprod(modprod(s1.b,s2.b),3)) % MOD;
res.b = (modprod(s1.a,s2.b) + modprod(s1.b,s2.a)) % MOD;
return res;
}

ullint p3array[65];
ullint p2array[65];
surd surdarray[65];

void init() {
p2array[1] = 2;
p3array[1] = 3;
surdarray[1].a = 2;
surdarray[1].b = 1;
for(int i = 2; i < 65; i++) {
p2array[i] = modprod( p2array[i-1] , p2array[i-1] );
p3array[i] = modprod( p3array[i-1] , p3array[i-1] );
surdarray[i] = mult(surdarray[i-1],surdarray[i-1]);
}
}

void solve(ullint a) {

if (a == 0 || a % 2 == 1) {
printf("0\n");
return;
}

a = a >> 1;

ullint p2 = 1;
ullint p3 = 1;
surd ps;
ps.a = 1;
ps.b = 0;

int i = 1;
while(a > 0) {
if ( (a & 1) == 1) {
p2 = modprod(p2, p2array[i]);
p3 = modprod(p3, p3array[i]);
ps = mult(ps,surdarray[i]);
}
i++;
a = a >> 1;
}

surd psminus;
psminus.a = modminus(2*ps.a, 3*ps.b);
psminus.b = modminus(2*ps.b, 3*ps.a);

ullint res1 = modprod(MODINV, (2*psminus.a + p3 + 2*p2 + 3) % MOD );
ullint res2 = 2*(2*ps.a + p3 + p2 + 1);

ullint res = modminus(res2, res1);
printf("%llu\n", res);
}

main() {

int T;
scanf("%d", &T);

int i;
init();
for(i = 0; i < T; i++) {

ullint a;
scanf("%llu", &a);

solve(a);
}
}

``````

## Stepping Numbers CodeChef Solution in C++14

``````#include <stdio.h>
#include <stdlib.h>

#define ullint unsigned long long
#define uint unsigned int

#define MOD 4294967143ULL
#define MODINV 1789569643ULL

typedef struct {
ullint a;
ullint b;
} surd;

inline ullint modprod(ullint a, ullint b) {
return (a*b) % MOD;
}

inline ullint modminus(ullint a, ullint b) {
a = a % MOD;
b = b % MOD;
if (a >= b)
return a - b;
else
return (MOD - b) + a;
}

inline surd mult(surd s1, surd s2) {
surd res;
res.a = (modprod(s1.a,s2.a) + modprod(modprod(s1.b,s2.b),3)) % MOD;
res.b = (modprod(s1.a,s2.b) + modprod(s1.b,s2.a)) % MOD;
return res;
}

ullint p3array[65];
ullint p2array[65];
surd surdarray[65];

void init() {
p2array[1] = 2;
p3array[1] = 3;
surdarray[1].a = 2;
surdarray[1].b = 1;
for(int i = 2; i < 65; i++) {
p2array[i] = modprod( p2array[i-1] , p2array[i-1] );
p3array[i] = modprod( p3array[i-1] , p3array[i-1] );
surdarray[i] = mult(surdarray[i-1],surdarray[i-1]);
}
}

void solve(ullint a) {

if (a == 0 || a % 2 == 1) {
printf("0\n");
return;
}

a = a >> 1;

ullint p2 = 1;
ullint p3 = 1;
surd ps;
ps.a = 1;
ps.b = 0;

int i = 1;
while(a > 0) {
if ( (a & 1) == 1) {
p2 = modprod(p2, p2array[i]);
p3 = modprod(p3, p3array[i]);
ps = mult(ps,surdarray[i]);
}
i++;
a = a >> 1;
}

surd psminus;
psminus.a = modminus(2*ps.a, 3*ps.b);
psminus.b = modminus(2*ps.b, 3*ps.a);

ullint res1 = modprod(MODINV, (2*psminus.a + p3 + 2*p2 + 3) % MOD );
ullint res2 = 2*(2*ps.a + p3 + p2 + 1);

ullint res = modminus(res2, res1);
printf("%llu\n", res);
}

main() {

int T;
scanf("%d", &T);

int i;
init();
for(i = 0; i < T; i++) {

ullint a;
scanf("%llu", &a);

solve(a);
}
}

``````

## Stepping Numbers CodeChef Solution in C

``````#include <stdio.h>

#define MOD 4294967143U

typedef unsigned int intu;
typedef unsigned long long longu;

longu s1[64],s2[64];

intu pmod(int a, longu n)
{
intu t;
longu s;

s=a;
t=1;

while(n)
{
if (n&1)
t=(s*t)%MOD;
s=(s*s)%MOD;
n>>=1;
}
return t;
}

intu pot(longu n)
{
longu q;
intu t1,t2;
int i;

t1=1;
t2=0;

for(i=0;n;n>>=1,i++)
if (n&1)
{
q=t1;
t1=(s1[i]*t1%MOD+3*(s2[i]*t2%MOD))%MOD;
q=s1[i]*t2%MOD+s2[i]*q%MOD;
if (q>=MOD)
t2=q-MOD;
else
t2=q;
}

return (94LL*t1+144LL*t2)%MOD;
}

int main()
{
int t,i;
longu n;

s1[0]=2;
s2[0]=1;
for(i=1;i<64;i++)
{
s1[i]=(s1[i-1]*s1[i-1]%MOD+3*(s2[i-1]*s2[i-1]%MOD))%MOD;
s2[i]=2*(s1[i-1]*s2[i-1]%MOD)%MOD;
}

scanf("%d",&t);

while(t--)
{
scanf("%llu",&n);

if (n&1)
{
printf("0\n");
continue;
}
n=n-1>>1;

printf("%llu\n",(21+11LL*pmod(2,n+2)+23LL*pmod(3,n+1)+pot(n))%MOD*1789569643%MOD);
}
return 0;
}``````
##### Stepping Numbers CodeChef Solution Review:

In our experience, we suggest you solve this Stepping Numbers CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Stepping Numbers CodeChef Solution.

Find on CodeChef

##### Conclusion:

I hope this Stepping Numbers CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.

Keep Learning!