arius1408's blog

How to know if a number N is divisible by k ? ( N <= 10^5000000) ?
By arius1408, history, 5 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 (14)
| Write comment?
»
5 years ago, hide # |
 
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
»
5 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

where can I submit code for the same ??

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

A problem based on this concept: 490C

→ Reply