### 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 ?

• +20

 » 7 weeks ago, # |   +106 bool check(string &n, long long k) { long long rem = 0; for (auto i : n) rem = ((rem * 10) + i - '0') % k; return rem == 0; } 
•  » » 7 weeks ago, # ^ |   +9 Thank for helping me out. Have a good day !!!
•  » » 7 weeks ago, # ^ |   0 why does it work?
•  » » » 7 weeks ago, # ^ |   +29 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$
•  » » » » 7 weeks ago, # ^ |   +5 Wow! That was impressive
•  » » » 7 weeks ago, # ^ |   +56 just take pen + paper and try dividing 6541691484 by 4231. He did the same but with code
•  » » » » 6 weeks ago, # ^ |   0 Wow. This little hint is easy enough to understand the code. Thank You!
•  » » 7 weeks ago, # ^ |   0 Nice bro.
 » 7 weeks ago, # |   -28 Here is the solution: https://m.youtube.com/watch?v=ub82Xb1C8os
 » 7 weeks ago, # |   +1 where can I submit code for the same ??
 » 7 weeks ago, # |   +2 A problem based on this concept: 490C
•  » » 6 weeks ago, # ^ |   0 this is also a good one problem