2

Задача была такова: есть "таблица умножения" размера 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;
}
4
  • 1
    Тема в общем тут не раз попадалась. Надо делать один цикл, перебирать числа только до корня из n и проверять, что остаток от деления на это число нулевой. В результат сразу прибавлять 2 кроме той итерации, где i == корень из k
    – CrazyElf
    8 сен 2020 в 7:50
  • Дайте-ка url, хочется убедиться, что O(N) достаточно будет...
    – Harry
    8 сен 2020 в 8:03
  • 1
    @CrazyElf В этом случае проверки до корня из N недостаточно. Нужна проверка до корня из k.
    – Harry
    8 сен 2020 в 8:26
  • @Harry конечно, я имел в виду корень из k, описка просто
    – CrazyElf
    8 сен 2020 в 9:11

3 ответа 3

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;
    }
}
2
  • Комментарии не предназначены для расширенной дискуссии; разговор перемещён в чат.
    – ЮрийСПб
    8 сен 2020 в 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
    9 сен 2020 в 4:03
4

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

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

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

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

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.