编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 166ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 25ms

├ 测试数据 10：答案正确... 166ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：357ms

...

高精度优化：

1、扩大进制（使用万进制）

2、乘2的时候不要一个一个地乘，一次乘15个2（32768），乘到最后还需要乘n个2，在一个一个地乘（或者打一个2的幂次表，two[i]=2^i ( i=15?15:k);

k-=newk;

for (int i=1;i0;i--)

{

outp[(125-i)*4]=mason[i]/1000+'0';

outp[(125-i)*4+1]=(mason[i]/100)%10+'0';

outp[(125-i)*4+2]=(mason[i]/10)%10+'0';

outp[(125-i)*4+3]=mason[i]%10+'0';

}

for (int i=0;i

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

月考前 晚上 做的~

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

编译通过...

├ 测试数据 01：答案正确... 56ms

├ 测试数据 02：答案正确... 619ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 244ms

├ 测试数据 10：答案正确... 603ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1522ms

太感谢Nimo了！

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

耶耶 秒杀

当然是看了别人的思路 要用二分来快速求幂

用分治

2^n=(2^(n div 2))^2*2^(n mod 2)

不过我的代码还是不错的（精简才是王道啊） 嘿嘿 拿来晒晒

---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|-

program p1223;

var p,k:longint;

ans,outi:array[0..1002] of longint;

procedure work(n:longint);

var i,j,x:integer;

begin

if n=0 then exit;

work(n div 2); //二分求

if odd(n) then x:=2 else x:=1; //判断如果是奇数的话就要多乘2

for i:=1 to 500 do

for j:=1 to 500 do

ans:=ans+outi[i]*outi[j]*x;

for i:=1 to 500 do //把答案存到outi[]里

begin

outi[i]:=ans[i] mod 10;

ans:=ans+ans[i] div 10;

end;

fillchar(ans,sizeof(ans),0); //每次清零

end;

begin

outi[1]:=1;

readln(p);

writeln(trunc(p*ln(2)/ln(10))+1);

work(p);

for k:=500 downto 2 do write(outi[k]);

writeln(outi[1]-1);

end.

编译通过...

├ 测试数据 01：答案正确... 41ms

├ 测试数据 02：答案正确... 462ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 166ms

├ 测试数据 10：答案错误...　├ 标准行输出

　├ 错误行输出

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：90 有效耗时：669ms

最后一点为什么不过。。。

感谢Nimo的提示，真的太有用了！

我开始有cena测，当数据取到310000时怎么都不行。但是用他的算法改了后就是0.1秒通过，暴爽的啊！

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|---|---|---|

贴下程序：

type atype=array[0..260]of longint;

var p,i,t:longint;

bin:array[0..30] of boolean;

a,b:atype;

function mul(a,b:atype):atype;

var i,j,k:longint;

begin

fillchar(mul,sizeof(mul),0);

if a[0]>126 then a[0]:=126;

if b[0]>126 then b[0]:=126;

for i:=1 to a[0] do

begin

k:=0;

for j:=1 to b[0] do

begin

mul:=mul+a[i]*b[j]+k;

k:=mul div 10000;

mul:=mul mod 10000;

end;

if k>0 then mul:=k;

end;

mul[0]:=i+j;

if k=0 then dec(mul[0]);

if mul[0]>126 then mul[0]:=126;

end;

procedure init;

var i:longint;

begin

read(p);

writeln(trunc(p*ln(2)/ln(10))+1);

i:=0;

while p>0 do

begin

bin[i]:=boolean(p mod 2);

p:=p div 2;

inc(i);

end;

t:=i-1;

a[0]:=1;

a[1]:=1;

b[0]:=1;

b[1]:=2;

end;

begin

init;

for i:=0 to t do

begin

if bin[i] then

a:=mul(a,b);

b:=mul(b,b);

end;

a[1]:=a[1]-1;

for I:=125 downto 1 do

write(a[i] div 1000,(a[i] mod 1000) div 100,(a[i] mod 100) div 10, a[i] mod 10);

end.

type

arr1=array[1..125]of longint;

var

st:string;

a,b:arr1;

e:array[1..30]of 0..1;

i2,j2,n,m,l,h,l1,jj:longint;

procedure cheng(var c,d:arr1);

var

i,j,k1:integer;

f:arr1;

begin

fillchar(f,sizeof(f),0);

for i:=1 to 125 do begin

k1:=0;

for j:=1 to 125-i+1 do begin

f:=f+c[i]*d[j]+k1;

k1:=f div 10000;

f:=f mod 10000;

end;

end;

c:=f;

end;

begin

readln(n);

m:=n;

l:=0;

while m>0 do begin

l:=l+1;

e[l]:=m mod 2;

m:=m div 2;

end;

a[1]:=2;

if e[1]=1 then b[1]:=2 else b[1]:=1;

for i2:=2 to l do begin

cheng(a,a);

if e[i2]=1 then

cheng(b,a);

end;

a:=b;

a[1]:=a[1]-1;

writeln(trunc(n*ln(2)/ln(10))+1);

jj:=0;

for i2:=125 downto 1 do begin

str(a[i2],st);

l1:=length(st);

if l1

这道题的难点在于求2的p次方。由于p的范围过大，所以要采用二分法快速求幂。即：A^p=A^(p div 2) * A(p div 2) (p为偶数)或A^p=A^(p div 2) * A(p div 2) * A (p为奇数)。把p转换为二进制的数字，存入数组B中，然后从二进制p的末位开始，ans:=1(A^0)，如果p=1，ans:=ans*A；如果p=0,ans:=ans*ans。

对于求2^p的位数，用换底公式即可。Log10(2^p)=p*ln(2)/ln(10)，然后加1再trunc即可。（因为10^n有n+1位，所以要加1）。

这道题要用高精度去做，我是编了两个过程，一个乘二，一个平方。刚开始是是高精度乘法忘了进位。解决了这个问题之后，又发现我又理解错了，要求最后500位，而我是把ans算到500位之后就跳出循环了。实际上只需要把ans计算到500位置后每次只计算后500位并且只保留500位即可。

在输出的时候要先判断ans的位数（lans）是否到了500位，如果没有到，则需要输出500-lans个0，并且50个换一下行，然后输出ans；如果lans>=500则直接输出并换行。

还有，别忘了把ans的末位减一！

回答者： robin5540 - 见习魔法师 二级 2008-7-10 15:03

快速求正整数次幂，当然不能直接死乘。举个例子：

3 ^ 999 = 3 * 3 * 3 * … * 3

直接乘要做998次乘法。但事实上可以这样做，先求出2^k次幂：

3 ^ 2 = 3 * 3

3 ^ 4 = (3 ^ 2) * (3 ^ 2)

3 ^ 8 = (3 ^ 4) * (3 ^ 4)

3 ^ 16 = (3 ^ 8) * (3 ^ 8)

3 ^ 32 = (3 ^ 16) * (3 ^ 16)

3 ^ 64 = (3 ^ 32) * (3 ^ 32)

3 ^ 128 = (3 ^ 64) * (3 ^ 64)

3 ^ 256 = (3 ^ 128) * (3 ^ 128)

3 ^ 512 = (3 ^ 256) * (3 ^ 256)

再相乘：

3 ^ 999

= 3 ^ (512 + 256 + 128 + 64 + 32 + 4 + 2 + 1)

= (3 ^ 512) * (3 ^ 256) * (3 ^ 128) * (3 ^ 64) * (3 ^ 32) * (3 ^ 4) * (3 ^ 2) * 3

这样只要做16次乘法。即使加上一些辅助的存储和运算，也比直接乘高效得多（尤其如果这里底数是成百上千位的大数字的话）。

我们发现，把999转为2进制数：1111100111，其各位就是要乘的数。

快速幂

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

终于ac了，怎么把b【100】(存储将p转化为2进制的数组）定义为全局变量就错。。。啊。。。

#include

#include

#define M 500

int main()

{

int a[M];long P;

int *p=a,jin=0,tem,i;

scanf("%ld",&P);

printf("%d\n", (int)(P * log10(2.0)) + 1);

*p=2;

for(i=1;i9)

{

*(p-1)-=10;

jin=1;

}

}

}

}

*a-=1;

for(i=1,p=a+M-1;p>=a;p--,i++)

{

printf("%d",*p);

if(i%50==0) printf("\n");

}

return 0;

}

Oms 类似快速幂的做法吧。。。

我大概认识快速幂，做了一下就A了

type

arr1=array[1..125]of longint;

var

st:string;

a,b:arr1;

e:array[1..30]of 0..1;

i2,j2,n,m,l,h,l1,jj:longint;

procedure cheng(var c,d:arr1);

var

i,j,k1:integer;

f:arr1;

begin

fillchar(f,sizeof(f),0);

for i:=1 to 125 do begin

k1:=0;

for j:=1 to 125-i+1 do begin

f:=f+c[i]*d[j]+k1;

k1:=f div 10000;

f:=f mod 10000;

end;

end;

c:=f;

end;

begin

readln(n);

m:=n;

l:=0;

while m>0 do begin

l:=l+1;

e[l]:=m mod 2;

m:=m div 2;

end;

a[1]:=2;

if e[1]=1 then b[1]:=2 else b[1]:=1;

for i2:=2 to l do begin

cheng(a,a);

if e[i2]=1 then

cheng(b,a);

end;

a:=b;

a[1]:=a[1]-1;

writeln(trunc(n*ln(2)/ln(10))+1);

jj:=0;

for i2:=125 downto 1 do begin

str(a[i2],st);

l1:=length(st);

if l1

#include "stdio.h"

#include "math.h"

int main()

{ int a[500]={0},d=0,i,j,p,len=1;

int t;

scanf("%d",&p);

a[0]=1;

t=(int)(p*log10(2.0))+1;

for(i=1;i

不用二分也可以，用2000ms左右

一定注意10个10个乘，即乘1048576

这道题可以利用二分法计算出2^p-1的后五百位，至于位数可以利用对数来求（n=p*log10(2)+1)