Поднятие целых чисел до высоких мощностей

Question

Пожалуйста, помогите мне с шагами по решению этой проблемы программирования на SPOJ: 7683. Powered and Squared.

Проблема заключается в том, чтобы поднять целые числа до очень высоких мощностей - до 10^120. Мощность, на которую должно быть поднята целое число, выражается в виде 250-значного числа в базе 3. Тривиальный алгоритм истекает, поскольку количество умножений безумно высока. Есть ли лучший подход?

Answer 1

Ключом к решению этой проблемы является осознание того факта, что «квадрат» в «быстром возведении по квадратам» не является магическим числом: это могут быть кубы или любая сила, которая вам нужна. Эта конкретная проблема требует возведения в степень по кубам, хотя, поскольку b записан в нотации base-3.

относительно легко расширить классический алгоритм работы с кубиками:

#include <cstdio> 
#include <cstdlib> 
#include <cstring> 

typedef long long i64; 

int main(int argc, char* argv[]) { 
    char buf[1024]; 
    fgets(buf, sizeof(buf), stdin); 
    int t = atoi(buf); 
    while (t--) { 
     fgets(buf, sizeof(buf), stdin); 
     char* b; 
     i64 a = strtol(buf, &b, 10); 
     // b points to the first space; find the second space 
     b = strchr(++b, ' '); 
     // This is where m begins 
     i64 m = atoi(b--); 
     a %= m; 
     i64 res = 1; 
     // We process b starting from the back 
     while (*b != ' ') { 
      if (*b == '1') { 
       res *= a; 
      } else if (*b == '2') { 
       // The part that differs from the classic algorithm is here: 
       res *= a*a; 
      } 
      res %= m; 
      // We do exponentiation by cubes, hence it's a*a*a 
      a = (a * a * a) % m; 
      // End of the interesting part 
      b--; 
     } 
     printf("%d\n", (int)res); 
    } 
    return 0; 
} 

Проблема в SPOJ устанавливается таким образом, что делает C++ I/O непозволительно медленно, так что вся эта раздражает манипуляции с характером указатели, к сожалению, необходимы.