题解 - Vijos

0

testla LV 7 @ 2009-10-30 23:20:32

var

s : string;

a,c : array[1..56]of qword;

n,i,j,h : longint;

procedure pf;

var

w : qword;

i,j,t : longint;

begin

fillchar(c,sizeof(c),0);

for i:=56 downto 1 do

begin

w:=0;t:=56;

if a[i]=0 then continue;

for j:=0 to 55 do

begin

if i-j=0 then break;

c:=c+a[t]*a[i];

c:=c+w;

w:=c div 1000000000;

c:=c mod 1000000000;

t:=t-1;

end;

end;

a:=c;

a[1]:=a[1] mod 100000;

end; { pf }

procedure c2;

var

t : qword;

i : longint;

begin

t:=0;

fillchar(c,sizeof(c),0);

for i:=56 downto 1 do

begin

c[i]:=a[i]*2;

c[i]:=c[i]+t;

t:=c[i] div 1000000000;

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

end;

a:=c;

a[1]:=a[1] mod 100000;

end;

procedure cqlt(ds: longint) ;

begin

if ds=2 then pf

else

if ds1 then

if odd(ds) then

begin

cqlt(ds div 2);

pf;

c2;

end

else

begin

cqlt(ds div 2);

pf;

end;

end;

begin

readln(n);

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

a[56]:=2;

cqlt(n);

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

str(a[1],s);

while length(s)

0

song19931218 LV 9 @ 2009-10-27 12:53:19

同楼下

0

fjlyzpcr LV 8 @ 2009-10-27 10:31:19

快速幂+高精

编译通过...

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

0

lucky1 LV 8 @ 2009-10-24 23:15:03

经典的二分迭代加高精度

有点难度

0

wllmh LV 10 @ 2009-10-23 18:57:35

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

0

ydd LV 10 @ 2009-10-22 16:45:07

用位运算艰难AC了

0

芒果木瓜榴莲 LV 9 @ 2009-10-11 21:04:42

赞楼下wnjgto的程序

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

0

LP.Fighting LV 10 @ 2009-10-11 20:41:44

好题!

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

普及组...orz

0

db_db_Jacky LV 10 @ 2009-10-06 20:22:11

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分快速幂 ~~~~

0

mynovoland LV 8 @ 2009-10-04 21:09:39

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

我擦好悬

0

laz LV 10 @ 2009-10-04 16:37:38

这个…………额

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

0

sy2006 LV 8 @ 2009-10-03 07:50:46

编译通过...

├ 测试数据 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行应该算比较短的吧哪位大牛可以具体分析一下二分啊谢过

0

sixhomeland LV 9 @ 2009-09-14 11:39:03

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

这就是差距啊！！！

0

maxint64 LV 7 @ 2009-09-05 09:26:26

编译通过...

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

0

LV 0 @ 2009-08-29 07:34:30

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

0

nblt LV 8 @ 2009-08-28 11:54:14

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我的!!!!

0

lishunzhi LV 9 @ 2009-08-28 11:08:50

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啊

0

aaa741852h LV 7 @ 2009-08-21 17:10:17

fuck!!!!!!!

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

0

sutank2009 LV 8 @ 2009-08-21 16:36:31

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

编译通过...

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

0

qzssy5618 LV 8 @ 2009-08-21 16:09:41

编译通过...

├ 测试数据 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：看了这三条还过不了哒？？）

题解

154 条题解

麦森数

信息

状态

开发

支持

题解

154 条题解

麦森数

信息

状态

开发

支持

还没有账户？

登录