Найти (num * (pow (b, p) - 1) / den)% mod, где p очень большое (10 ^ 18) - PullRequest
Новая
       22

Найти (num * (pow (b, p) - 1) / den)% mod, где p очень большое (10 ^ 18)

0 голосов
/ 25 июня 2019

Я хочу найти (num * (pow (b, p) - 1) / den)% мод.Я знаю о бинарном возведении в степень.Но мы не можем сделать это прямо.Гарантируется, что числитель делится на знаменатель.Это означает, что ограничения

[num * (pow (b, p) - 1)]% den == 0

для мода: 1 <= mod <= 10 ^ 9 и мод можетбыть простым или составным </p>

ограничения на b: 1 <= b <= 10 </p>

ограничения на p: 1 <= p <= (10 ^ 18) </p>

ограничения наnum: 1 <= num <= (10 ^ 9) </p>

ограничения на ден: 1 <= den <= (10 ^ 9) </p>

Здесь pow (b, p) означает поднятое bк власти р (б ^ р).Гарантируется, что числитель делится на знаменатель.Как я могу сделать это с бинарным возведением в степень

1 Ответ

1 голос
/ 25 июня 2019

Ваше выражение должно быть переписано, чтобы упростить его. Сначала позвольте k = num / den, с k целым числом в соответствии с вашим вопросом.

Итак, вы должны вычислить
(k & times; (b ^ p-1)) mod m = ((k mod m) & times; ((b ^ p -1) mod m)) mod m
= ((k mod m) & times; ((b ^ p mod m) -1 mod m) mod m) mod m
= ((k mod m) & times; ((b ^ p mod m) + m-1) mod m) mod m (1)

Итак, настоящая проблема - вычислить b ^ p mod m

Многие языки (python, java и т. Д.) Уже имеют модульное возведение в свои стандартные библиотеки. Обратитесь к документации и используйте ее. В противном случае, здесь реализация C. 

unsigned long long modexp(unsigned long long b, unsigned long long e, unsigned long long m) {
  if (m==1) return 0;
  unsigned long long res=1;
  unsigned long long bb = b % m;
  while (e) {
    if (e & 1) 
      res = (res*b) % m;
    e >>= 1;
    bb = (bb*bb) % m;
  }
  return res;
}

Реализация использует long long для соответствия вашим ограничениям. Он опирается на классический прием двоичного возведения в степень. Все значения b ^ l, где l - степень двух (l = 2 ^ t), вычисляются и сохраняются в var bb, и если установлен соответствующий бит t th для e, это значение b ^ l интегрируется в результат. Битовое тестирование выполняется путем проверки последовательных четностей e при сдвиге e вправо на каждом шаге.

Наконец, тот факт, что (a & times; b) mod m = ((a mod m) & times; (b mod m)) mod m используется, чтобы избежать вычислений для очень больших чисел. У нас всегда есть res

Тогда вам просто нужно применить (1), чтобы получить окончательный результат.

РЕДАКТИРОВАТЬ в соответствии с точностью, указанной в комментариях
Чтобы вычислить n = (3 ^ p-1) / 2 mod m, можно заметить, что
(3 ^ p-1) / 2 = x * m + n (поскольку 3 ^ p-1 является четным, x является целым числом, 0 & leq; n 3 ^ р-1 = х * 2 * м + 2n (0 & le; 2n <2 м) <br> поэтому 2n = (3 ^ p-1) мод 2m

Мы можем просто применить предыдущий метод с модулем 2 * m и разделить результат (который будет четным) на 2.

...