/*首先考虑2的p次方减1有多少位。
因为2的p次方的个位只能是2，4，6，8，所以减1后和2的p次方*的
位数相同。
这里可以使用double log10(double
x)函数。分析为什么？
这个地方要学会分析*/
/*其次分析2的p次方末500位怎么求？
显然，对于任何p>0,考虑p的二进制形式，不难得到：
P = a020 + a121 +
a222 + … + an-12n-1 +
2n
这里，ai要么是1，要么是0.
因而：
2p = 2a0 * 22a1 *
24a2 * 28a3 * … *
2an-12n-1 *
22n(这里给大家解释下，因为无法编辑出来，所以口头说明下：2an-12n-1是2的an-1*2n-1次方，同理22n是2的2n次方)。
这里用数组来存放大整数，数组的一个元素对应于十进制大整数的
一位。如果本题也这么做，就会超时。
为了加快计算速度，可以用一个数组元素对应于大整数的四位，
即将大整数表示为10000进制，而数组中的每一个元素就存放10000
进制数的一位。
例如：存放6373384，那么只需要2个元素就可以了，a[0] = 3384,
a[1] = 637
因为要存放500个数，而一个数组元素表示4位10进制，所以只需要
125个元素就可以了。
*/
#include #include #include #include #include #include using namespace std; #define LEN 125 //每个数组元素存放十进制的4位，因此数组最 多只要125个元素即可 /* Multiply函数的功能是计算高精度乘法 a * b 结果的末500位放在 a 中 */ void Multiply(int *a, int *b) { int i, j; int nCarry; //存放进位 int nTmp; int c[LEN]; //存放结果的末500位 memset(c, 0, sizeof(int)*LEN); //现开始写成500居 然没结果 for(i = 0; i < LEN; i++) { nCarry = 0; //考虑下面为什么是LEN-i,因为 i+j < LEN,否 则c会越界。 for(j = 0; j < LEN - i; j++) { nTmp = c[i+j] + a[j]*b[i] + nCarry; c[i+j] = nTmp % 10000; nCarry = nTmp / 10000; } } memcpy(a, c, LEN * sizeof(int)); } int main() { int i; int p; int anPow[LEN]; //存放不断增长的2的次幂 int aResult[LEN]; //存放最终结果的末500位 scanf("%d", &p); printf("%d/n", (int)(p * log10(2.0))+1); //下面将2的次幂初始化为2^(2^0) //最终结果为1 anPow[0] = 2; aResult[0] = 1; for(i = 1; i < LEN; i++) { anPow[i] = 0; aResult[i] = 0; } //下面计算2的p次方 while(p > 0) { if(p & 1) Multiply(aResult, anPow); //如果 ai的值为1，则将最终结果乘以2的2的 i 次方 p >>= 1; Multiply(anPow, anPow); //计算2的2的 (i+1)次方，用2的2的 i 次方乘以2的2的 i 次方 } aResult[0]--;//2的p次方算出后减1 //输出结果 for(i = LEN-1; i >= 0; i--) { if(i % 25 == 12) printf("%02d/n%02d", aResult [i]/100, aResult[i] % 100); else { printf("%04d", aResult[i]); if(i % 25 == 0) printf("%/n"); } } return 0; } |