將整數提高到大功率

Question

請幫助我解決SPOJ上編程問題的步驟：7683. Powered and Squared。

該問題要求將整數提高到很高的功率 - 高達10^120。整數提升的能力用基數3中的250位數表示。平凡的算法超時，因爲乘法的次數非常高。有更好的方法嗎？

Answer 1

解決這個問題的關鍵是實現「方塊快速求冪」中的「square」不是一個幻數：它可以是立方體或任何你想要的功率。不過，這個特殊的問題要求立方體取冪，因爲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過於緩慢，因此這整個討厭的操縱與性格不幸的是，指針是必要的。