алгоритм — lcm всех чисел в массиве в переполнении стека
Я наткнулся на этот фрагмент кода для вычисления наименьшего общего множителя из всех чисел в массиве, но не смог понять используемый алгоритм. Какая польза от __builtin_popcount здесь, который используется для подсчета количества установленных бит?
pair<long long, int> pre[200000];
long long a[25], N;
long long trunc_mul(long long a, long long b)
{
return a <= INF / b ? a * b : INF;
}
void compute()
{
int limit = 1 << N;
limit--;
for (int i = 1; i <= limit; i++)
{
long long lcm = 1;
pre[i].second = __builtin_popcount(i);
int k = 1;
for (int j = N - 1; j >= 0; j--)
{
if (k&i)
{
lcm = trunc_mul(lcm / __gcd(lcm, a[j]), a[j]);
}
k = k << 1;
}
pre[i].first = lcm;
}
return;
}
Решение
Предоставленный вами отсканированный код содержит до 25 номеров. Для каждого подмножества чисел он вычисляет их LCM в pre[i].first и количество их в этом подмножестве в pre[i].second, Само подмножество представляется как битовая маска, поэтому для вычисления количества элементов в подмножестве, который использует фрагмент __builtin_popcount, Это не имеет ничего общего с вычислением LCM.
LCM вычисляется с использованием довольно стандартного подхода: LCM любого набора чисел равен их произведению, деленному на их GCD. Это именно то, что делает этот фрагмент, используя встроенную функцию GCD __gcd,
k&i а также k = k<<1 часть состоит в том, чтобы выяснить, какие числа принадлежат множеству, представленному битовой маской. Если вы не до конца понимаете, попробуйте посмотреть, что произойдет, если i = 0b11010, запустив этот цикл на листе бумаги или в отладчике. Вы заметите, что k&i условие будет выполнено на второй, четвертой и пятой итерации, а именно на позициях, в которых i имеет единицы в своем двоичном представлении.
Другие решения
Других решений пока нет …