arius1408's blog

How to know if a number N is divisible by k ? ( N <= 10^5000000) ?
By arius1408, history, 3 years ago, In English

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 ?

  • Vote: I like it
  • +20
  • Vote: I do not like it

Comments Comments (15)
| Write comment?
»
3 years ago, # |
  Vote: I like it +106 Vote: I do not like it 
bool check(string &n, long long k) {
    long long rem = 0;
    for (auto i : n)
        rem = ((rem * 10) + i - '0') % k;
    return rem == 0;
}
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Thank for helping me out. Have a good day !!!

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    why does it work?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +29 Vote: I do not like it

      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$$$
      → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +56 Vote: I do not like it

      just take pen + paper and try dividing 6541691484 by 4231. He did the same but with code

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Wow. This little hint is easy enough to understand the code. Thank You!

        → Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    from where you got this relation i mean the website you learned math from it

    → Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

where can I submit code for the same ??

→ Reply
»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

A problem based on this concept: 490C

→ Reply