-1
請幫助我解決SPOJ上編程問題的步驟:7683. Powered and Squared。將整數提高到大功率
該問題要求將整數提高到很高的功率 - 高達10^120。整數提升的能力用基數3中的250位數表示。平凡的算法超時,因爲乘法的次數非常高。有更好的方法嗎?
請幫助我解決SPOJ上編程問題的步驟:7683. Powered and Squared。將整數提高到大功率
該問題要求將整數提高到很高的功率 - 高達10^120。整數提升的能力用基數3中的250位數表示。平凡的算法超時,因爲乘法的次數非常高。有更好的方法嗎?
解決這個問題的關鍵是實現「方塊快速求冪」中的「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過於緩慢,因此這整個討厭的操縱與性格不幸的是,指針是必要的。
這是一個家庭作業嗎?答案是*快速求冪*。 – Alexander 2012-02-17 20:13:23
不只是練習,請給出逐步解決方案不知道該怎麼辦 – user1217059 2012-02-17 20:27:10
快速求冪還有兩個問題: 1.b可以上升到3^250,所以計算a^b可能是不合理的。 2.b是在基地3,傳達到基地10將花費很多我認爲 – user1217059 2012-02-17 20:36:46