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

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;
}

Тема в общем тут не раз попадалась. Надо делать один цикл, перебирать числа только до корня из n и проверять, что остаток от деления на это число нулевой. В результат сразу прибавлять 2 кроме той итерации, где i == корень из k — CrazyElf, Sep 08 '20 at 07:50
Дайте-ка url, хочется убедиться, что O(N) достаточно будет... — Harry, Sep 08 '20 at 08:03
@CrazyElf В этом случае проверки до корня из N недостаточно. Нужна проверка до корня из k. — Harry, Sep 08 '20 at 08:26
@Harry конечно, я имел в виду корень из k, описка просто — CrazyElf, Sep 08 '20 at 09:11

Harry · Accepted Answer · 2020-09-08T09:01:54.697

5

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

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;
    }
}

edited Sep 08 '20 at 09:01

answered Sep 08 '20 at 08:08

Harry

221,325

Комментарии не предназначены для расширенной дискуссии; разговор перемещён в чат. – ЮрийСПб Sep 08 '20 at 14:40
@Mikhajlo Чтоб закрыть этот вопрос - Страуструп написал примерно так - что он согласен с моим мнением (что безопаснее писать const char*), и что char* - проблема исторического свойства (*I agree, but it is hard to mess with the ancient past - you don't know who you might hurt. I *think* I tried this and failed almost 40 years ago.). Поскольку формально я получил разрешение делать так, если мой компилятор это позволяет (You might simply accept both*), так что, признавая стандарт, я из принципа оставляю все как есть, пока мне не покажут хоть один компилятор, который это не примет :) – Harry Sep 09 '20 at 04:03

score 4 · Answer 2 · answered Sep 08 '20 at 07:51

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

KoVadim · Answer 3 · 2020-09-08T08:28:40.797

0

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

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--;}

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

edited Sep 08 '20 at 08:28

answered Sep 08 '20 at 08:03

KoVadim

112,121
6
94
160

Упс... Навскидку взятые 235 и 432 у вас дают ответ 14, в то время как правильный - 18... Где именно прокол, я не копался. Впрочем - кажется, не тот случай, когда можно ограничиться корнем из N. – Harry Sep 08 '20 at 08:14
Нужна проверка до корня из К. – Harry Sep 08 '20 at 08:20
я потестил первый вариант (там где без корня и оно дает ответ 18). – KoVadim Sep 08 '20 at 08:26
О том и спич - тестировать до корня из N мало, надо до корня из K. – Harry Sep 08 '20 at 08:27

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

3 Answers3

Linked