Необходимо найти количество чисел из диапазона (A, A+B] (A, B < 10^9), не содержащих простых делителей, меньших k (k < 300). Пробую перебирать произведения простых чисел, меньших k, и использовать формулу включения-исключения, примерно вот так:
int go(int count, int product, int prime_index)
{
if (product > B || prime_index == primes.size())
return 0;
int product_new = primes[prime_index] * product;
int count_new = count+1;
int result = 0;
if (count_new & 1)
{
result += (B / product_new - A / product_new);
}
else
{
result -= (B / product_new - A / product_new);
}
result += go(count+1, product_new, prime_index + 1);
result += go(count, product, prime_index + 1);
return result;
}
TL. Возможно ли как-нибудь ускорить данное решение или необходим другой подход? Спасибо.
Интуитивно — это должно работать. Сейчас попробую)
Первое, что приходит в голову при взгляде на код —
в этой строке возможно переполнение, со всеми вытекающими последствиями.
Upd. Да, написал идейно такое же решение, оно проходит.
можно перебирать простые не по возрастанию индекса, а по убыванию. Уже 293*283*281*277>10^9
Это не имеет значения.
Если бы это был перебор в стиле "найдите хоть один подходящий вариант" — тогда да, в таких задачах подобные оптимизации часто являются жизненно важными.
А здесь нам нужно рассмотреть ровно все варианты из множества подходящих, поэтому такая оптимизация ничем не поможет — разве что порядок перебора изменится на противоположный, но общее число состояний должно остаться таким же.
На практике — так и получается, у меня решение с reverse(prime.begin(),prime.end()); отработало за 0.265, решение без этой строки — тоже за 0.265.
Наоборот, если перебирать в возрастающем порядке, можно сделать оптимайз: если при умножении на текущее простое получается больше чем нужно, то следующие не просматривать. А при переборе в другую сторону так не получится:)
Еще такой момент, когда ты вычисляешь product_new, он уже может быть больше чем B, тем не менее ты вычисляешь result += (B / product_new — A / product_new); и запускаешь снова рекурсию go(count, product, prime_index + 1); хотя там к ответу заведомо ничего не прибавится. Этот вызов порождает такой-же новый и фактически программа работает в primes.size() раз дольше.