' Негізгі идеясы, біз сандарды көп рет бөле алмаймыз. Әрбір санды ең көп дегенде \(log(n)\) рет бөлуге болады.

\(N = 10^6\) болсын – максималды сан. \(cnt[x]\) массивін енгізейік, ол \(N\) өлшемді және массивтегі \(x\) мәнінің қанша рет кездесетінін есептейді. Жаңарту \(d\) келгенде, барлық \(d\) көбейткіштері үшін келесі кодты орындаймыз, егер қажет болса:

\(for\ (k = d;\ k \le N;\ k\ += d)\)

\(\ \ \ \ cnt[k / d] += cnt[k]\)

\(\ \ \ \ cnt[k] = 0\)

Бұл жолдарды орындағанда жиынтығын қайта есептеп отырамыз. Егер қандай да бір сәтте \(d\) сұрауына ештеңе өзгермегенін байқасақ, болашақта сол сұрау үшін ештеңе жасамасақ болады (мысалы, \(cnt[d] = -1\) деп белгілейміз). Бұл жағдайда, әрбір \(d\) үшін \(N/d\) секіріс жасаймыз және әр секірістер сериясын ең көп дегенде \(\log_d(N)\) рет орындаймыз. Жалпы операциялар саны: \[\sum_{d=1}^N N/d \cdot \log_d(N) = O(N \ln(N) \log(N)),\] және біз тек \(N\) бүтін сандардан тұратын 1 массивті қолданамыз.

Основная идея в том, что много раз мы делить числа не сможем. Каждое число можно разделить не более чем \(log(n)\) раз.

Пусть \(N = 10^6\) – максимальное число. Заведем массив \(cnt[x]\) размера \(N\) который считает сколько раз встречается значение \(x\) в массиве. Когда приходит обновление \(d\), выполним для всех множителей \(d\) следующий код, если требуется:

\(for\ (k = d;\ k \le N;\ k\ += d)\)

\(\ \ \ \ cnt[k / d] += cnt[k]\)

\(\ \ \ \ cnt[k] = 0\)

И при выполнении этих строк пересчитывать сумму. Поймем, что если в какой-то момент для запроса \(d\) мы ничего не изменили, то мы можем это запомнить и в будущем для такого же запроса ничего не делать (например сделать \(cnt[d] = -1\)). Тогда, для каждого \(d\) мы выполним \(N/d\) прыжков, и каждую серию прыжков сделаем максимум \(\log_d(N)\) раз. Итого операций \[\sum_{d=1}^N N/d \cdot \log_d(N) = O(N \ln(N) \log(N)),\] и мы используем только 1 массив из \(N\) интов.