math - How to check for division by 7 for big number in C++?

Question

I have to check, if given number is divisible by 7, which is usualy done just by doing something like n % 7 == 0, but the problem is, that given number can have up to 100000000, which doesn't fit even in long long.

Another constrain is, that I have only few kilobytes of memory available, so I can't use an array.

I'm expecting the number to be on stdin and output to be 1/0.

This is an example

34123461273648125348912534981264376128345812354821354127346821354982135418235489162345891724592183459321864592158
0

It should be possible to do using only about 7 integer variables and cin.get(). It should be also done using only standard libraries.

Answer 1

you can use a known rule about division by 7 that says: group each 3 digits together starting from the right and start subtracting and adding them alternativly, the divisibility of the result by 7 is the same as the original number:

ex.:

testing 341234612736481253489125349812643761283458123548213541273468213
        549821354182354891623458917245921834593218645921580

   (580-921+645-218+593-834+921-245+917-458+623-891+354-182
    +354-821+549-213+468-273+541-213+548-123+458-283+761-643
    +812-349+125-489+253-481+736-612+234-341 
    = 1882 )
    % 7 != 0 --> NOK!

there are other alternatives to this rule, all easy to implement.