факторизационная оптимизация чисел

Question

Как оптимизировать этот код с учетом N<=1000?Я пробовал факторизацию каждого числа, но это отнимает много времени:

cnt = 0 ;
 for int i=1 to N
    for int j=1 to N
        for int k=1 to N
        if(i*j)%k==0 
         cnt = cnt + 1

Answer 1

Итак, вы делаете перерасчет:

Для каждой пары i, j, которая имеет значение x = i * j, вы запускаете цикл k раз, но есть множество пар i * j, которые дают одинаковое значение

И вы используете модуль N ^ 3 раза, помните, что модуль стоит дорого.

Оптимизация:

1. Вместо перерасчета всех пар i * j сохраните их в хэш-таблице / массиве и посчитайте их частоту

2. Вместо использования модуля используйте некоторые математические выражения для оптимизации, когда некоторое число x, деленное на k, дает по модулю 0? только когда x кратно k, поэтому просто циклически изменяйте частоты от 0 до n * n с шагом k

Пример кода (c ++):

vector<int>freq(n*n+1); //that's just array of n*n+1 zeroes

for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
    freq[i*j]++;

int cnt = 0;
for(int k=1; k<=n; k++)
    for(int j=0; j<=n*n; j+=k) //note these loops look like n^3 at first glance yet it's something like n log (n*n) (check harmonic number if you're curious why)
    cnt+=freq[j];

Еще больше оптимизаций:

Что ж, 1000 - это немного, даже если числа занимают 64 бита каждое, то есть ~ 8 КБ памяти. Таким образом, у вас есть возможность сгенерировать все ответы в некотором массиве, например, answer [n] сохраняет ответ для некоторого n, а затем массив кодов ответов в коде.