### arius1408's blog

By arius1408, history, 7 weeks ago, Um, hi ... ? Basically we have a number N (N <= 10^5000000) represented by a string. Let say that |N] = the length of string N. Now I'm given an integer k (k <= 1e9). How do I confirm that N is divisible by k in O(|N|) ??

P/S : Notice that I want solution that works in O(|N|), not O(|N|log5000000). Anyone can help me ? Comments (12)
 » bool check(string &n, long long k) { long long rem = 0; for (auto i : n) rem = ((rem * 10) + i - '0') % k; return rem == 0; } 
•  » » Thank for helping me out. Have a good day !!!
•  » » why does it work?
•  » » » Think it as DP: if $a_1 a_2 \dots a_{n-1} \mod k = r_{n-1}$then $a_1 a_2 \dots a_n \mod k = (10 a_1 a_2 \dots a_{n-1} + a_n) \mod k = (10 r_{n-1} + a_n) \mod k$
•  » » » » Wow! That was impressive
•  » » » just take pen + paper and try dividing 6541691484 by 4231. He did the same but with code
•  » » » » Wow. This little hint is easy enough to understand the code. Thank You!
•  » » Nice bro.
 » Here is the solution: https://m.youtube.com/watch?v=ub82Xb1C8os
 » where can I submit code for the same ??
 » A problem based on this concept: 490C
•  » » this is also a good one problem