Блог пользователя NotImplemented

Автор NotImplemented, 11 лет назад, По-русски

Timus 1940

Необходимо найти количество чисел из диапазона (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. Возможно ли как-нибудь ускорить данное решение или необходим другой подход? Спасибо.

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Интуитивно — это должно работать. Сейчас попробую)

Первое, что приходит в голову при взгляде на код —

int product_new = primes[prime_index] * product;

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

Upd. Да, написал идейно такое же решение, оно проходит.

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится

Возможно ли как-нибудь ускорить данное решение?

можно перебирать простые не по возрастанию индекса, а по убыванию. Уже 293*283*281*277>10^9

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    Это не имеет значения.

    Если бы это был перебор в стиле "найдите хоть один подходящий вариант" — тогда да, в таких задачах подобные оптимизации часто являются жизненно важными.

    А здесь нам нужно рассмотреть ровно все варианты из множества подходящих, поэтому такая оптимизация ничем не поможет — разве что порядок перебора изменится на противоположный, но общее число состояний должно остаться таким же.

    На практике — так и получается, у меня решение с reverse(prime.begin(),prime.end()); отработало за 0.265, решение без этой строки — тоже за 0.265.

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    Наоборот, если перебирать в возрастающем порядке, можно сделать оптимайз: если при умножении на текущее простое получается больше чем нужно, то следующие не просматривать. А при переборе в другую сторону так не получится:)

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Еще такой момент, когда ты вычисляешь product_new, он уже может быть больше чем B, тем не менее ты вычисляешь result += (B / product_new — A / product_new); и запускаешь снова рекурсию go(count, product, prime_index + 1); хотя там к ответу заведомо ничего не прибавится. Этот вызов порождает такой-же новый и фактически программа работает в primes.size() раз дольше.