C ++ деление по модулю
Я хочу рассчитать результат этого уравнения
[(pow(4, p) - 1) / 3] % q
Я написал функцию pow это возвращает p-ую степень 4 mod q, но я не могу применить это здесь.
Как мне это сделать?
p, q являются целыми числами и могут быть большими — до 1 000 000 000.
Заранее спасибо.
Решение
подсчитывать pow(4, p) - 1 по модулю 3*qи разделите результат на 3. Для возведения в степень используйте Модульное возведение в степень алгоритм.
Редактировать: Это даст вам целочисленное деление (то есть округление результата). Смотрите ответ @ lisyarus для деления в кольце целых чисел по модулю q,
Если q не делится на 3, тогда оба ответа должны давать одинаковый результат, потому что pow(4, p) - 1 всегда делится на 3, поэтому округление целочисленного деления в игру не входит. Если q делится на 3, то нет мультипликативного обратного, и может использоваться только этот метод.
Другие решения
Это зависит от того, что вы подразумеваете под делением на 3. Если это нормальное целочисленное деление, кажется, что @interjay ответил на это. Если это деление на 3 в кольце целых чисел по модулю p, то вы должны найти обратное к 3 по модулю p, если оно существует.
detector