Ускоренный способ проверить, является ли число делимым с определенным номером

Question

#include <iostream> 

using namespace std; 

int main() 
{ 
    long long n, k; 

    cin >> n >> k; 

    int num, count = 0; 

    do{ 
     n--; 
     cin >> num; 
     if (num > 99 && (num % 10) % k == 0){ 
      //cout << num << endl; 
      count++; 
     } 
     else if(num < 100 && (num % k) == 0){ 
      //cout << num << endl; 
      count++; 
     } 
    }while(n); 

    cout << count << endl; 

    return 0; 
} 

Я пишу программу для проверки того, делится ли конкретное число на определенный номер, введенный пользователем.

п = количество чисел вводится к = число, чтобы проверить, если номера делятся

Моя программа работает очень хорошо до сих пор, но она превышает на срок. Есть ли более быстрый алгоритм или код, чем этот, чтобы проверить, является ли число делимым с другим конкретным номером?

Ссылка: http://www.codechef.com/problems/INTEST/

Answer 1

Прежде всего, проблема здесь заключается в том, чтобы считывать номера с входа в быстрый путь, не делая деления. Имея это в виду, вот некоторый код для быстрого чтения:

vector<char> buffer(n * 10); // allocate a large buffer 
cin.read(&buffer[0], buffer.size()); // fill the buffer with chars from input 
buffer.resize(cin.gcount()); // cut buffer size to number of chars actually read 
... 

Это читает весь входной файл (обратите внимание на размер буфера, который ограничен каждым числом, имеющим менее 10 цифр).

Затем преобразуйте последовательность символов в числа и проверьте каждое число для делимости на k (num % k != 0, как отмечали другие). Код для этого можно найти в «сложном» решении, которое вы разместили (он занимает всего одну строку кода).

Answer 2

Modulo оператор (%) является то, что вы хотите. Пример:

if (k != 0) 
    return n % k == 0; 

или для пространства блюстителей:

if (k != 0) 
    return !(n % k); 

Модульное возвращает остаток от деления между двумя числами, например, 5% 2 возвращает 1. Если остаток равен 0, то число делятся (IE 4% 2 вернет 0).

http://en.wikipedia.org/wiki/Modulo_operation

Answer 3

Вместо этого фрагмента кода

cin >> num; 
    if (num > 99 && (num % 10) % k == 0){ 
     //cout << num << endl; 
     count++; 
    } 
    else if(num < 100 && (num % k) == 0){ 
     //cout << num << endl; 
     count++; 
    } 

Вы могли бы просто написать

cin >> num; 
    count += num % k == 0; 

Answer 4

Точка 'проблемы' является то, что стандартные/O библиотеки I для большинства языков являются очень общей целью и, следовательно, не могут быть оптимальными инструментами для чтения или записи данных, когда формат четко определен, а производительность имеет решающее значение.

В этом случае вы используете функции библиотеки для чтения из потоков ввода-вывода, которые сильно абстрагированы от базовой системы хранения. Как правило, чем ближе вы к аппаратным средствам, тем быстрее будет работать ваш код.

Я хотел бы начать, пытаясь использовать C файл ввод-вывод функции, такие как fopen и fread читать большой кусок двоичных данных из файла в память, а затем обработать эту память сканирования для чисел «на месте» и подсчитывать правильные Матчи. Петля до тех пор, пока у вас не будет больше строк для обработки, и помните, что много более эффективно читать большие блоки данных, которые маленькие.

Answer 5

Вместо использования если (n% k!= 0) use, int quotient = n/k; if (quotient * k == n)

Оператор модуля медленнее второго подхода. (Мне понадобилось 4,5 секунды, чтобы запустить код с оператором модуля и 1 секунду со вторым подходом)