Modulo of a 100k-digit number
c, modulus
Solution
There are many tricks that you can do to make modular arithmetic easier. For example, suppose you want to know what 1234567890 mod 17 is, but you don't have a numeric type big enough to represent 1234567890. Well, what do we know about `%`, assuming all numbers are positive?
(a+b)%e == ((a%e)+(b%e))%e
(c*d)%e == ((c%e)*(d%e))%e
If you don't understand why these identities are true, go back to the definition of `%` and study them until you have this solid.
Now that we know that, we know that
1234567890 % 17 = (12345 * 100000 + 67890) % 17
= ((((12345 % 17) * (100000 % 17)) % 17) + (67890 % 17)) % 17
And now you have only much smaller numbers. If those numbers are still too big, keep breaking them down until they're small enough.
I answered a very similar question on the Math StackExchange site; it might also be of help to you.
https://math.stackexchange.com/questions/91583/implementing-fermats-primality-test/91584#91584
Problem
For numbers `n` and `m` I need to evaluate `n % m`. The catch is `n` can be as big as `10^100000`, `m` maxes out at `10^18`. `unsigned long long` is about `2^64` (please correct me if I'm wrong) which won't do, then I thought I could read it in array of characters, but how to calculate remainder of character. Is there any way to reduce that number to a smaller number so it could be transferred from char array to `unsigned long long` (like `atol` but for `long long` instead of `long`). Also I think I would be needing a faster way to do %, because time limit is 0.1s Any help is appreciated.