同楼下

快速幂+高精

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

program ex;

var i,j,n,ans:longint;

now,t:array[0..1000]of longint;

procedure arrange;

var i,j:longint;

begin

for i:=1 to 500 do

begin

inc(now,now[i] div 10);

now[i]:=now[i] mod 10;

end;

end;

procedure g(x:longint);

var i,j:longint;

begin

if x=0 then

begin

now[1]:=1;

exit;

end;

g(x div 2);

fillchar(t,sizeof(t),0);

for i:=1 to 500 do

for j:=1 to 500 do

inc(t,now[i]*now[j]);

if x and 1=1 then

for i:=1 to 500 do t[i]:=t[i]*2;

now:=t;

arrange;

end;

begin

readln(n);

g(n);

ans:=trunc(n*ln(2)/ln(10))+1;

writeln(ans);

dec(now[1]);

for i:=1 to 500 do

if now[i]

经典的二分迭代加高精度

有点难度

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

快速幂不会，用压位惊险AC

用位运算艰难AC了

赞楼下wnjgto的程序

我还不太会二分快速幂的说……

好题!

快速幂忘了,第二次做还耗我1h...

普及组...orz

2分就是说

x:=2^n

n若为奇数

x:=2^(n div 2)*2^(n div 2)*2

n为偶数

X:=2^(n div 2)*2^(n div 2)

只要计算2^(n div 2) 就好了。。对于每个2^(n div 2)都进上面操作

复杂度自然降下来。。

就是所谓的2分快速幂 ~~~~

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

我擦 好悬

这个…………额

程序写的长了点、不过 AC了就好~~

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

Vivid Puppy

还好不是Sunny 否则就别想秒杀了

呵呵 说一下思路

位数：不多说了 看了大牛们的题解就知道位数直接输了

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

高精度计算：

不理解什么叫二分法，自己琢磨半天，想了种二进制乘方法

想法如下：

比如要算2^7 就把它拆成2^4*2^2*2^1

可得2^7=2^(2^2)*2^(2^1)*2^(2^0)

而(2^(2^0))^2=2^(2^1);(2^(2^1))^2=2^(2^2);

通过这种转化就可以快速得到乘方结果

如何分解？

我的分解方式是把指数转换为2进制（第一位表示二进制的最后一位，第二位表示倒数第二位，依此类推） 如果第i位上是1，就说明分解结果里有2^(i-1)

于是就有了可以用log2n时间乘方的方法（对于任何底数都适用）

其实这道题没必要压位

以下是程序实现：

var n,i,tw:longint;

a:array[1..3,0..501] of longint;

two:array[1..31] of 0..1;

procedure mul(s1,s2,s3:longint);//高进度不压位乘法，把数组s1与数组s2相乘的结果保存在s3

var i,j:longint;

begin

for i:=1 to 500 do

for j:=1 to 501-i do a[s3,i+j-1]:=a[s3,i+j-1]+a[s1,i]*a[s2,j];//懒得去判断位数 直接把500位写在这了

for i:=1 to 499 do begin a[s3,i+1]:=a[s3,i+1]+a[s3,i] div 10;a[s3,i]:=a[s3,i] mod 10;end;

a[s3,500]:=a[s3,500] mod 10;//首位处理一下

end;

begin

readln(n);

i:=n;

while i0 do begin inc(tw);two[tw]:=i mod 2;i:=i div 2;end;//说明里提到的转换二进制的过程 储存在数组two

writeln(trunc(n*ln(2)/ln(10))+1);//输出位数

a[1,1]:=1;a[2,1]:=2;//初值，1是最终结果数组，2是当前被分解的数的数组，3是临时数组

for i:=1 to tw do begin

if two[i]=1 then begin//如果为1就乘上这个当前被分解的数

fillchar(a[3],sizeof(a[3]),0);mul(1,2,3);a[1]:=a[3];end;

fillchar(a[3],sizeof(a[3]),0);mul(2,2,3);a[2]:=a[3];end;//乘出下一个被分解的数

for i:=500 downto 2 do begin

write(a[1,i]);

if (i-1) mod 50=0 then writeln;end;

writeln(a[1,1]-1);//输出 最后一位减1

end.

程序不长 才26行 应该算比较短的吧 哪位大牛可以具体分析一下二分啊 谢过

Vivid Puppy:

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

Vijos Sunny:

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

这就是差距啊！！！

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

没有0ms全灭 牛们不要笑话菜呀

想到了先乘 p div 25 次 2^25，然后再乘p mod 25次2---|-20;（超时）

看牛们的题解才知道 位数可以直接算出来trunc(ln2/ln10*p)+1---|-ac;

nblt，see程序是不好的，不道德的，不诚实的，你怎么能鼓励别人see程序呢？请回答我的问题，不要逃避哦！！！！！！

type p1=array[1..10000]of longint;

var

a,b:array[1..10000]of longint;

p,i,j:longint;

procedure tot(var a:p1;b,c:p1);

var

i,j,x:longint;

begin

fillchar(a,sizeof(a),0);

for i:=1 to 500 do

begin

x:=0;

for j:=1 to 500 do

begin

a:=b[i]*c[j]+x+a;

x:=a div 10;

a:=a mod 10;

end;

a:=x;

end;

end;

begin

readln(p);

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

fillchar(a,sizeof(a),0);

fillchar(b,sizeof(b),0);

a[1]:=1;

b[1]:=2;

while p>0 do

begin

if p mod 2=1 then tot(a,a,b);

tot(b,b,b);

p:=p div 2;

end;

for i:=10 downto 1 do

begin

for j:=50 downto 1 do

if (i=1)and(j=1) then write(a[(i-1)*50+j]-1)

else write(a[(i-1)*50+j]);

writeln;

end;

end.

程序数我最明了!大家快来see我的!!!!

var n,leng,v:longint;

a:array[0..19]of longint=(1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288);

c:array[-3..1000000]of longword;

procedure cheng(x:longword);

var i:longint;

begin

for i:=1 to leng do c[i]:=c[i]*x;

for i:=1 to leng-1 do

begin

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

c[i]:=c[i] mod 10;

end;

i:=leng;

while (c[i]>=10)and(i0 then c[500]:=c[500] mod 10;

leng:=i;

end;

procedure init;

var i:longint;

begin

readln(n);

end;

procedure main;

var i:longint;

begin

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

c[1]:=1;

leng:=1;

for i:=1 to n div 20 do cheng(1048576);

cheng(a[n mod 20]);

end;

procedure outit;

var i:longint;

begin

dec(c[1]);

for i:=500 downto 1 do write(c[i]);

end;

begin

init;

main;

outit;

end.

我就不服了,为什么又AC啊

fuck!!!!!!!

交了N遍都50，浪费了N久，原来‘0’写成o，把longint写成integer

楼下的看着啦！！！秒杀！！

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

program mason;

var

n:longint;

i,j:longint;

out:array[1..500] of longint;

sta:array[1..1000] of longint;

procedure solve(n:longint);{用二分法求2的n次幂}

begin

if n=0 then

exit;

solve(n div 2); {二分}

for i:=1 to 500 do

for j:=1 to 500 do

if n mod 2=0

then {如果是偶数，就计算平方}

sta:=sta+out[i]*out[j]

else {是奇数就计算平方并且*2}

sta:=sta+out[i]*out[j]*2;

for i:=1 to 500 do

begin

out[i]:=sta[i] mod 10;

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

end;

for i:=1 to 1000 do sta[i]:=0

end;

begin

readln(n);

writeln(trunc(ln(2)/ln(10)*n)+1);{输出位数，用对数算后+1}

out[1]:=1;

solve(n);

for i:=500 downto 2 do

begin

write(out[i]);

if i mod 50=1 then writeln{换行}

end;

writeln(out[1]-1);

end.

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

给WA牛的忠告：

1、在做2的N次幂的时候，可以先乘N div 20次的1048576，再乘N mod 20次的2（感谢syh73牛的题解）

2、不做多余的运算，只算500位，多出的进位一概抹去

3、位数=p*ln 2/ln 10+1（感谢thebeet牛的题解）

（ps：看了这三条还过不了哒？？）

编译通过...

├ 测试数据 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