Краткий ответ: для практической вычислительной задачи «точное целое значение» оптимально — быстрый алгоритм возведения в степень (возведение в степень методом бинарного возведения) для $3^{100}$ и $2^{100}$ с последующим вычитанием $3^{100}-2^{100}$. Если же среда не поддерживает большие целые числа, предпочтительнее реконструировать результат по модулю малого множества машинных простых модулей (CRT). Ниже сравнение и рекомендации.
1) Бинарное возведение в степень + вычитание
- Идея: вычислить $3^{100}$ и $2^{100}$ методом возведения в степень «возведение в степень по двоичному экспонуенту» (exponentiation by squaring), затем выполнить вычитание.
- Формулы/слово: за $O(\log n)$ умножений получить $a^n$. Например, для $3^{100}$ и $2^{100}$ делаем по примерно $O(\log 100)$ больших умножений.
- Сложность: примерно $O(\log n)$ больших целочисленных умножений, размер промежуточных чисел — $O(n\log a)$ бит (для $3^{100}$ ≈ $100{\log }_{2}3\approx 159$ бит).
- Плюсы: простая реализация, минимальный код, быстро и эффективно при наличии библиотеки работы с большими целыми (bigint). Для нашей задачи (около 160 бит) — очевидный выбор.
- Минусы: требует поддержки больших целых; если среда ограничена машинными словами (32/64 бита) и нет bigint, прямое хранение результата невозможно.
2) Вычисление по модулю + восстановление через CRT (Chinese Remainder Theorem)
- Идея: выбрать набор простых модулей $m_1,m_2,\dots ,m_k$ машинного размера (например 32- или 64-бит), вычислить остатки $r_i\equiv 3^{100}-2^{100}(\mathrm{mod}{m}_i)$ (каждый по модульному быстрому возведению), затем восстановить единственное целое значение в диапазоне $[0,M-1]$, где $M={\prod }_i{m}_i$, если $M$ превышает предполагаемый размер результата.
- Формула/условие: нужно $M>3^{100}$ (или по модулю абсолютного предела результата), тогда CRT даёт точное восстановление.
- Сложность: нужно примерно $k$ модульных возведений (каждое $O(\log n)$ операций над машинными словами) и один алгоритм CRT (Garner) — общий объём работы часто ниже по памяти, так как все операции выполняются в пределах машинного слова.
- Плюсы: подходит, когда отсутствует bigint, но доступно много 32/64‑бит операций; легко параллелится; хорош при очень больших степенях/основаниях, когда результат слишком велик, чтобы хранить в памяти целиком.
- Минусы: необходимо подобрать достаточно модулей (их произведение > итогового числа); реализация CRT немного сложнее; накладные расходы на восстановление.
3) Альтернативы и замечания
- Разложение $3^{100}-2^{100}=(3-2){\sum }_{k=0}^{99}{3}^{99-k}{2}^k={\sum }_{k=0}^{99}{3}^{99-k}{2}^k$ формально верно, но здесь $3-2=1$, поэтому это не уменьшает сложность — сумма из 100 членов и так большой. Можно использовать рекуррент $S_{n+1}=3S_n+2^n$ для поэтапного вычисления, но это требует $O(n)$ умножений и потому хуже бинарного метода по времени.
- Если требуется только остаток по какому‑то модулю (делимость, проверка), то прямое модульное возведение (без CRT) — самый экономный вариант.
- Для очень больших $n$ и/или баз лучше выбирать бинарное возведение в сочетании с быстрыми алгоритмами умножения (FFT‑умножение) или CRT/разделяй‑и‑властвуй в зависимости от возможностей машины.
Рекомендации конкретно для $3^{100}-2^{100}$:
- На обычной машине с bigint: применить бинарное возведение к $3$ и $2$, затем вычесть — самый простой и быстрый подход.
- В среде без bigint, но со 64‑бит арифметикой: вычислять остатки по нескольким 64‑бит простым модулям и восстановить через CRT (количество модулей таково, чтобы их произведение > $3^{100}$).