Как найти делитель, чтобы увеличить остаток?

Question

Приведенные два номера n и k, найти x, 1 <= x <= k, что максимально уменьшает остаток n % x.

Например, n = 20 и k = 10, решение равно x = 7, потому что остаток 20% 7 = 6 максимален.

---

Мое решение это:

int n, k; 
cin >> n >> k; 
int max = 0; 
for(int i = 1; i <= k; ++i) 
{ 
    int xx = n - (n/i) * i; // or int xx = n % i; 
    if(max < xx) 
    max = xx; 
} 
cout << max << endl; 

Но мое решение O(k). Есть ли более эффективное решение?

Answer 1

Не асимптотически быстрее, но быстрее, просто отступая назад и останавливаясь, когда вы знаете, что не можете добиться большего.

Предполагается, что k составляет менее n (в остальном только результат k).

int max = 0; 
for(int i = k; i > 0 ; --i) 
{ 
    int xx = n - (n/i) * i; // or int xx = n % i; 
    if(max < xx) 
    max = xx; 
    if (i < max) 
    break; // all remaining values will be smaller than max, so break out! 
} 
cout << max << endl; 

(Это может быть дополнительно улучшена, выполнив цикл до тех пор, как i > max, тем самым устраняя один условный оператор, но я написал это таким образом, чтобы сделать его более очевидным)

Кроме того, проверьте Garey и Книга Джона Джонса и книга о нецелесообразности, чтобы убедиться, что это не NP-Complete (я уверен, что я помню некоторую проблему в этой книге, которая очень похожа на это). Я бы сделал это, прежде чем вкладывать слишком много усилий, пытаясь найти лучшие решения.

Answer 2

Приятная маленькая головоломка!

Начиная с двух тривиальных случаев.

для n < k: любая x с.т. n < x <= k решает.

для n = k: x = floor(k/2) + 1 решает.

Мои попытки.

для n > k:

x = n 
while (x > k) { 
    x = ceil(n/2) 
} 

^---- Не работает.

1. x = floor(float(n)/(floor(float(n)/k) + 1)) + 1
2. x = ceil(float(n)/(floor(float(n)/k) + 1)) - 1

^---- "Закрыть" (независимо от того, что это означает), но не работает.

Мои гордость склоняет меня сказать, что я был первым, чтобы использовать самый большой k -ограниченного гармоники, задаваемый 1.

Solution.

Инлайн с другими ответами я просто проверить гармоники (термин любезность @ColonelPanic) от n менее k, ограничивая в соответствии с настоящим максимальным значением (любезно @TheGreatContini). Это лучшее из обоих миров, и я успешно тестировал со случайными целыми числами от 0 до 10000000.

int maximalModulus(int n, int k) { 
    if (n < k) { 
     return n; 
    } 
    else if (n == k) { 
     return n % (k/2 + 1); 
    } 
    else { 
     int max = -1; 
     int i = (n/k) + 1; 
     int x = 1; 
     while (x > max + 1) { 
      x = (n/i) + 1; 
      if (n%x > max) { 
       max = n%x; 
      } 
      ++i; 
     } 
     return max; 
    } 
} 

Тесты производительности: выход http://cpp.sh/72q6

Пример:

Average number of loops: 
bruteForce: 516 
theGreatContini: 242.8 
evgenyKluev: 2.28 
maximalModulus: 1.36 // My solution 

Answer 3

Я неправильно точно, но он смотрит на меня, что это зависит от того, если n < k или нет.

Я имею в виду, если n < k, n%(n+1) дает вам максимум, поэтому x = (n+1).

Ну, с другой стороны, вы можете начать с j = k и вернуться оценки n%j, пока не будет равна n, таким образом x = j является то, что вы ищете, и вы получите его в максимально k шаги ... Слишком много , это?

Answer 4

машет руками вокруг

Нет Значение x, которое является фактором n может производить максимальную n%x, так как если x является фактором n тогда n%x=0.

Таким образом, вам нужна процедура, которая позволяет избежать любых x, что является фактором n. Но это означает, что вам нужен простой способ узнать, является ли фактор x. Если бы это было возможно, вы могли бы сделать простой простой факторизации.

is notis not Известный простой способ выполнения простой факторизации не может быть «простым» способом решения вашей проблемы (я не думаю, что вы собираетесь найти одну формулу, необходим какой-то поиск).

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

Answer 5

Для k> n задача тривиальна (возьмите x = n + 1).

Для k < n, подумайте о графике остатков n% x. Он выглядит одинаково для всех n: остатки опускаются до нуля на гармониках n: n/2, n/3, n/4, после чего они вскакивают вверх, затем плавно уменьшаются к следующей гармонике.

Решение - самый правый локальный максимум ниже k. В качестве формулы x = n//((n//k)+1)+1 (где // - целочисленное деление).

Answer 6

Эта задача эквивалентна нахождению максимума функции f(x)=n%x в заданном диапазоне.Давайте посмотрим, как эта функция выглядит следующим образом:

Очевидно, что мы могли бы получить максимум раньше, если мы начнем с x=k, а затем уменьшить x в то время как это не имеет никакого смысла (до x=max+1). Также эта диаграмма показывает, что для x больше, чем sqrt(n), нам не нужно уменьшать x последовательно. Вместо этого мы могли сразу перейти к предыдущему локальному максимуму.

int maxmod(const int n, int k) 
{ 
    int max = 0; 

    while (k > max + 1 && k > 4.0 * std::sqrt(n)) 
    { 
     max = std::max(max, n % k); 
     k = std::min(k - 1, 1 + n/(1 + n/k)); 
    } 

    for (; k > max + 1; --k) 
     max = std::max(max, n % k); 

    return max; 
} 

Волшебное константа 4.0 позволяет повысить производительность за счет уменьшения числа итераций первой (дорогой) петли.

Худшая временная сложность случая может быть оценена как O (min (k, sqrt (n))). Но для достаточно большого k эта оценка, вероятно, слишком пессимистична: мы могли бы найти максимум намного раньше, и если k значительно больше sqrt(n), нам нужно всего 1 или 2 итерации, чтобы найти его.

Я сделал несколько тестов, чтобы определить, сколько итераций необходимо в худшем случае при различных значениях n:

n  max.iterations (both/loop1/loop2) 
10^1..10^2 11 2 11 
10^2..10^3 20 3 20 
10^3..10^4 42 5 42 
10^4..10^5 94 11 94 
10^5..10^6 196 23 196 
up to 10^7 379 43 379 
up to 10^8 722 83 722 
up to 10^9 1269 157 1269 

темпы роста заметно лучше, чем O (SQRT (п)).