C++ деление по модулю

Question

Я хочу вычислить результат этого уравнения

[(pow(4, p) - 1) / 3] % q

Я написал функцию pow это возвращает p-ую степень 4 mod q, но я не могу применить это здесь. Как мне это сделать?

p, q являются целыми числами и могут быть большими - до 1 000 000 000.

Заранее спасибо.

Answer 1

Подсчитывать pow(4, p) - 1 по модулю 3*qи разделите результат на 3. Для возведения в степень используйте алгоритм модульного возведения в степень.

Редактировать: Это даст вам целочисленное деление (т.е. округление результата). Смотрите ответ @lisyarus для деления в кольце целых чисел по модулю q,

Если q не делится на 3, тогда оба ответа должны давать одинаковый результат, потому что pow(4, p) - 1 всегда делится на 3, поэтому округление до целочисленного деления не вступит в игру. Если q делится на 3, тогда нет мультипликативного обратного, и может использоваться только этот метод.

Answer 2

Это зависит от того, что вы подразумеваете под делением на 3. Если это нормальное целочисленное деление, кажется, что @interjay ответил на это. Если это деление на 3 в кольце целых чисел по модулю p, то вы должны найти обратное к 3 по модулю p, если оно существует.