-2

Есть формула:

RESULT = (CONST + var) % MOD

RESULT - целое число, >= 0

CONST, var, MOD - целые числа, > 0

Вопрос:

Как изменится var, если:

  • MOD увеличить на 1
  • MOD уменьшить на 1

При этом RESULT и CONST не должны измениться.

Не брутфорсом.

2
  • Если по условию mod > 0 и =1, то mod-1 = 0, тогда решения не будет. Это я так, к слову) Это, кстати, может быть одним из решений
    – daydark
    10 ноя 2016 в 6:56
  • а точно больше нет никаких ограничений?
    – Grundy
    10 ноя 2016 в 7:18

1 ответ 1

2

Нашёл решение. Исходное уравнение

RESULT = (CONST + var) % MOD

Пусть, NEWMOD - увеличенный или уменьшенный MOD.

var = NEWMOD - (CONST - RESULT) % NEWMOD

На примерах.

На исходном примере.

(25 + 15) % 16 = 8
  • CONST = 25
  • var = 15
  • MOD = 16
  • RESULT = 8

Увеличиваем:

NEWMOD = MOD + 1 = 17

var = 17 - (25 - 8) % 17 = 17 - 0 = 17

(25 + 17) % 17 = 8

Уменьшаем:

NEWMOD = MOD - 1 = 15

var = 15 - (25 - 8) % 15 = 15 - 2 = 13

(25 + 13) % 15 = 8

UPD: что касается доказательства.

Перенесём результат на другую часть равенства или, проще сказать, уменьшим обе части на значение результата.

Т.к. в правой части у нас не деление, а остаток от него, то это допустимо.

CONST + var >= RESULT

, т.к. RESULT это остаток от деления

(25 - 8 + var) % 16 = 0 => (17 + var) % 16 = 0

Другими словами (частный случай):

17 + var = 16 => var = 16 - 17 = -1

(25 + (-1)) % 16 = 8

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

В данном случае: -1, 15, 31, 47 и т.д.

3
  • А доказательство?
    – cronfy
    10 ноя 2016 в 8:00
  • @cronfy (N-(C-R)%N+C)%N = 0 - C+R+C = R
    – Harry
    10 ноя 2016 в 11:10
  • доказательство добавил в ответ
    – Vitaly
    10 ноя 2016 в 11:29

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.