CareerCup

The above algorithm is a good idea and can be modified to be correct.

short mod(byte[] a, short b)
{
int result = 0;

/* start from the left (the higher digits), get two bytes (so as to match b) each time
* to mod b. The result should be less than b. Then add the result with the next two
* bytes to mod b, and the result should less than b again. And repeat. If the a.size()
* is an odd number, there will be one byte left at last. Then we handle that one byte
* after the loop.
*/
for (int i = 0; i < a.size()-1; i+=2) {
result = (result * 256*256 + a[i] * 256 + a[i+1]) % b;
}

if(a.size()%2==1) {
result = (result * 256 + a[a.size()-1]) % b;
}


return static_cast<short>(result);
}

My Solution:
I still use 93,143,913 => (5,141,67,105)
93143913 = 5*2^24+141*2^16+67*2^8+105*2^0

we calculate 93,143,913 % 20
start from right(because we could reuse 2^8%20):

105%20 = 5 2^0%20 = 1, so for 105*2^0, the remainder should be 5*1 = 5
67%20 = 7 2^8%20 = 16, so for 67*2^8, the remainder should be (7*16)%20 = 12
141%20 = 1 2^16%20 = 16, so for 141*2^16, the remainder should be (1*16)%20 = 16
5%20 = 5 2^24%20 = 16, so for 5*2^24, the remainder should be (5*16)%20 = 0

at last, (0+16+12+5)%20 = 13
It is equal with original number modulo 20;

Please verify it!

Big int is 123456 is represented as a[0]=6, a[1]=5...a[5]=1

int genMod(byte *a, int start, int end, byte *b) {
  byte number=b[0]+(10*b[1]);
  if(start>end) return;  
  elseif (start=end) return a[start]%number;
  int temp = a[start]+(10*a[start+1]);
  temp = temp%number;
  return (((genMod(a, start+2, end, b))*(100%number))%number + temp)%number;
}

Logic: 123456 % 45 = (1234*100+56)%45 = (((1234%45)*(100%45))%45 + (56%45))%45

short getMod(char* A, short m, int Alen){
   int retVal = 0;  //this is A % m

   for(int i = 0; i < Alen; ++i){
	rem = (A[i] + 256 * rem) % m;
   }
   return rem;
}

This is like anonymous's answer, but you need to do: result = (a[i] + 256 * result) % b; !!

void Main()
{
var bigInt = new int[] {1,2,3,4,5,6,7,8,9,1,1,1,2,1,3,1,4,1,5,1,6,1,7};
var smallInt = 121;
var previousMod = 0;
foreach (var i in bigInt)
{
previousMod = (previousMod * 10 + i) % smallInt;
}
previousMod.Dump();
}

I think, in this problem "a" is very big integer and given as a byte array. For example 93,143,913 will be { 5, 141, 67, 105 } (msb is 0th byte). This way you can represent arbitrarily large integers as it happens in crypto. The solution will be take each byte and multiply with 2^8 and the previous mod and then take the mod with "b". Here is the code:

short mod(byte[] a, short b)
{
    int result = 0;
    for (int i = 0; i < a.size(); ++i)
        result = (a[i] * 256 + result) % b;

    return static_cast<short>(result);
}

a represents one large integer you cannot store internally. the mod would only concern values less than that which can be stored in a variable the size of b (2 bytes in this case)