I have got 3 numbers a,b and m(m is prime). a is very very large(around 10^10^5). I have to calculate (floor(a/b))%m. Since a is very large, so I have stored 'a' as string then calculated value of a under mod m using code below:
long long int len = a.length();
long long int ans=0;
for(long long int i = 0; i<len;i++){
ans=(ans*10 + (a[i]-'0'))%m;
}
return ans;
Then I simply multiplied above value with the multiplicative mod inverse of b(I have calculated multiplicative mod inverse of b using fermat's little theorem.)
But this is not the desired answer. This will give me exact value of (a/b)%m. But I have to calculate (floor(a/b))%m.
Example: a=7, b=2 and m=5. Since a can be very very large(10^10^5), I just cant store 'a' directly. I must store it under mod m. So now a becomes 2(7%5 = 2).
Now I perform (a/b)%m=(2/2)%5 = 1. But my actual answer should have(floor(7/2)%5)=3%5=3.
I am stuck here. Can anyone help me to get the desired answer.
I would store the numbers as arrays of $1$s and $0$s in binary. If $a$ is of order $10^{10^5}$ that is only about $300,000$ words of memory. You need to write a function that divides two numbers of this type. The neat thing is that if $b$ is $n$ bits long, you just need to see if $b$ is greater than or less than the first $n$ bits of $a$. If it is, write down a $1$ in the answer and subtract $b$ from $a$. If not, it will be less than the first $n+1$ bits of $a$, so write a $01$ and subtract $b$ again. Once you have subtracted $b$, write as many $0$s as needed to get back to $n$ bits of what is left of $a$. We are implementing binary long division. When $b$ is greater than the rest of $a$ quit and you have $\lfloor \frac ab \rfloor=c$. Now you take $c$ and divide it by $m$ the same way, but you keep the remainder instead of the quotient.
Of course, you can handle much larger numbers if you store as ints instead of bits, but the programming will be harder.