Блог пользователя arius1408

How to know if a number N is divisible by k ? ( N <= 10^5000000) ?
Автор arius1408, история, 3 года назад, По-английски

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
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +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;
}
→ Ответить
»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

where can I submit code for the same ??

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

A problem based on this concept: 490C

→ Ответить