Big Multiplication

[hellon]

Hey, Can anyone tell that how can we multiply two very big numbers of length 10^5 with a modulo.

[tpb]

If the modulus is 3 then we've just had this question.

[helios]

(x * y) % n = ((x % n) * (y % n)) % n

[4z86RXSz]

use boost library in c++ or big integer library in c++

else

the two number are in string format

for ex

"1234567"

now what would be the remainder is 1234567 is divide by 3

it would be

(1+2+3+4+5+6+7)%3=1

so you just have to add each char of the string -'0' and then calculate % with 3

[legion07]

@iamdad3 I have used boost library, but still getting WA. I don't understand why because boost library is providing precision upto 1024.

[tpb]

legion07 wrote:

I have used boost library, but still getting WA. I don't understand why because boost library is providing precision upto 1024.

1024 what? If it's decimal digits then it's not enough since the OP said the problem needs up to 10000 digits. If it's 1024 bits (which is the case if you're referring to the cpp_int backend), then it's only about 308 decimal digits (divide by log(10)/log(2) or about 3.322). To have room for 10000 decimal digits you need at least 33230 bits.

#include <boost/multiprecision/cpp_int.hpp>
#include <iostream>

namespace mp = boost::multiprecision;

typedef mp::number<mp::cpp_int_backend<1024, 33333, mp::unsigned_magnitude,
                   mp::unchecked, void> > uint33333_t;

int main() {
    uint33333_t n(1); // start at 1
    // double it 33230 times (result is > 10000 decimal digits long)
    for (int i = 0; i < 33230; i++) n *= 2;
    std::cout << n << '\n'; // output this to a file and look at the file size
}

But as has already been mentioned, the problem doesn't need multiprecision numbers anyway (if this is the "modulo 3" problem).

[ghostrideriit]

store digits in a string and use sum of digits property