what are the meaning of that ?
the first test case :
i get a binary number then ----- i convert it to decimal and get 220 :) that's right
the second test case :
i get a binary number then------i convert it to decimal i get a very large number
the problem here i can't convert it to satisfy this condition
456 % 7 = 1
You probably need this page: http://en.wikipedia.org/wiki/Modular_arithmetic
The reason it is used in contests is usually that the normal result of something would be very large, and big numbers are a hassle in many languages.
What happens is that the numbers 1000101101... in this problem can have many bits. A lot more bits than 64. So, it is hard to first convert it to decimal and then get the remainder.
If you grab a calculator app that supports very large numbers, I think that even windows' does it, you can see the real conversion of that bit sequence is : 1431663726, if you calculate the mod, you will get: 659433
Since there will be many more bits than 64, in this problem it is best to calculate the modulo on the go instead of first calculating the decimal value and then the modulo.
So you will have a huge string
s = "101010101010101010101110111110000...."
The usual way to convert that to int is:
res = 0
for i = 0 , i < n { res = res * 2 + int( s[i] ) }
res = res % 1000003
With modular arithmetic, you will see that you can do:
res = 0
for i = 0 , i < n { res = (res * 2 + int( s[i] ) ) % 1000003 }
And it will give the wanted result without causing overflow.
You need to see "Modular arithmetic".
Since you asked to output only "modulo 10^6+3 ".
You can, at each step while converting from bin. to dec. , take modulo 10^6 + 3, that way the number never exceeds Integer range.
Example :
Binary number : 110
Decimal conversion Process :
Expected Answer = ((2^0)*0 + (2^1)*1 + (2^2)*1) % (1000003);
Modular arithmetic tells us:
(A + B) % M is equivalent to (A%M + B%M)%M;
so at each step find the modulus, that is :
Final Answer = ((2^0)*0% (1000003) + (2^1)*1% (1000003) + (2^2)*1% (1000003))% (1000003);