整数を高倍率にする

Question

SPOJでこのプログラミング問題を解決する手順を手伝ってください：7683. Powered and Squared

この問題では、整数を非常に高いパワー（最大10^120）にする必要があります。整数が上乗せされるべき乗は、3進数で250桁の数字で表されます。乗算の回数が非常に多いので、簡単なアルゴリズムがタイムアウトします。より良いアプローチがありますか？

Answer 1

この問題を解決するための鍵は、「正方形による高速累乗」の「正方形」が魔法の数ではないという事実の実現です。それは、立方体でも、あなたが望む力でもかまいません。この特定の問題は、bがベース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が極端に遅くなりますように設定されているので、文字でこの全体の迷惑な操作されポインタは、残念ながら、必要です。