### Divisiblity by 3

Below given c++ code for division spoj or Divisiblity by 3 spoj.

First see the divisibility of number ‘X’ by three when
written in binary form .

**A binary number is a multiple of 3 if and only if the alternating sum of its bits is also a multiple of 3**

let see for some ‘X’:-

4 = 100 1 - 0 + 0 = 1, not multiple of 3

6 = 110 1 - 1 + 0 = 0, multiple of 3

78 = 1001110 1 - 0 + 0 - 1 + 1 - 1 + 0 = 0, multiple of 3

109 = 1101101 1 - 1
+ 0 - 1 + 1 - 0 + 1 = 1, not multiple of 3

Now we have to find how many numbers exist in decimal
form(base 10) such that when converted into binary(base 2) form has N length
and is divisible by 3.(I will call this n as binary length)

Now let’s start with length N=1;

N=1 = 0 ->divisible by 3
total = 1;

N=2 then (00) &
(11) is divisible by 3 , Total = 2;

N=3 We can see that all number of binary length less than 3
will present in it

1-> 000

2-> 011

3-> 110

For N=3 total 3 number are possible.

Similarly we will get for all other number. Now will se how
to calculate it for large number ,for that we have to find relation between
them. Let’s derive that ->

N=1 ->1

N=2 ->2 (2*1)

N=3 ->3 (2*1)*2 - 1

N=4 -> 6 (2^2 -1)*2

N=5 ->11 (2^3 –
2^1)*2 - 1

N=6 ->22 (2^4 –
2^2 -1) *2

N=7 ->43 (2^5 –
2^3 – 2^1)*2 - 1

From the above we can find out that if ‘N’ is

**then:-***even*
Total number divisible by three will be given by->

**2**^{n-1 }- (2 + 2^{3}+ 2^{5}+…….+ 2^{n-3})

Similarly for

**one->***odd***2**^{n-1 }- (1+2 + 2^{3}+ 2^{5}+…….+ 2^{n-3})

On reducing the above we will get

**For EVEV -> (2**

^{n}+ 2)/3**ODD -> (2**

^{n}+ 1)/3

Hence our complexity reduces to O(log n) because we can find
(a

^{b }MOD P) in logarithmic time.#include <bits/stdc++.h> using namespace std; #define ULL unsigned long long #define MOD 1000000007 #define INV 333333336 //Inverse modulo of 3 with 1000000007 ULL pow_mod(ULL n) { ULL x=1,p=2; while(n) { if(n&1) x=(x*p)%MOD; p=(p*p)%MOD; n>>=1; } return x; } int main() { ULL n,result; while(scanf("%llu",&n)!=EOF) { if(n&1){ result = ((pow_mod(n)+1)*INV)%MOD; printf("%llu\n",result); } else{ result = ((pow_mod(n)+2)*INV)%MOD; printf("%llu\n",result); } } return 0; }