Как можно ускорить работу кода?

Question

Задача была такова: есть "таблица умножения" размера n * n, нужно указать какое количество раз встречается в таблице число k. То что я написал работает, но когда дело доходит до чисел 1e6, то поиск чисел занимает слишком много времени. А нужно укладываться в 0.5 сек, подскажите пожалуйста.

#include <iostream>
using namespace std;
int num;

int main()
{
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        for (int z = 1; z <= n; z++)
        {
            unsigned long h;
            h = i * z;
            if (h == k)
            {
                num++;
            }
        }
    }
    cout << num;
    return 0;
}

Answer 1

Вместо того, чтобы генерировать всю таблицу, достаточно разложить число k на множители всеми способами, например, проверив на делимость k на числа от 1 до корня из k

Answer 2

В Вашем случае код имеет сложно квадратичную. Ее очень легко свести к линейной, убрав внутренний цикл. То есть, вместо

for (int z = 1; z <= n; z++)
{
  unsigned long h;
  h = i * z;
  if (h == k)
  {
    num++;
  }
}

Запишем так

if (k % i == 0) {
  int z = k / i;
  if (z <= n) {
      num++;
  }
}

Но зачем проверять аж до n, если можно проверять только до корня с n, а потом просто умножить на два? правда нужно отдельно обработать случай, когда h == n*n (это как раз нужно учитывать только раз).

У меня получилось где то так

for (int i = 1; i <= sqrt(k); i++)
{
    if (k % i == 0) {
        int z = k / i;
        if (z <= n) {
            num++;
        }
    }
}
num *=2;
int sq = (int)sqrt(n);
if (sq*sq == n) { num--;}

Да, этот код выглядит ужасненько, но думаю, он будет не медленнее разложения на множители и последующей игре с ними.

Answer 3

Достаточно проверки в один проход -

int main(int argc, const char * argv[])
{
    int n, k;
    cin >> n >> k;
    if (k > n*n) { cout << 0 << endl; return 0; }
    int count = 0;
    for(int i = 1; i <= n; ++i)
    {
        if (k%i == 0 && k/i <= n) count++;
    }
    cout << count << endl;

}

Ну, наверное, можно и еще ускорить... но что-то мне кажется, что этого O(N) должно хватить.

Ускорение - проверка не до N, а до корня из K с удвоением результата. Цикл при этом выглядит так:

for(int i = 1; i <= sqrt(k)+0.5; ++i)
{
    if (k%i == 0 && k/i <= n)
    {
        count+=2;
        if (k/i == i) --count;
    }
}

БЛОГ НА HUSL

Как можно ускорить работу кода?

Ответы (3 шт):