154 条题解
-
0
victorygod LV 5 @ 2009-02-13 11:18:37
#include
#include
using namespace std;main()
{
long n,t;
int a[3000],b[3000],c[10000],p[100];
memset(p,0,sizeof(p));
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
int la=1,ln=0,lb=1,lc=0;
a[1]=2;b[1]=1;
cin>>n;
cout -
0
type hp=array[0..2000] of longint;
var
i,j,n,m:longint;
a,b:hp;
c:array[0..1000] of longint;
procedure chen(a,b:hp;var c:hp);
var
len,i,j:longint;
begin
fillchar(c,sizeof(c),0);
for i:=1 to a[0] do
for j:=1 to b[0] do
begin
c:=a[i]*b[j]+c;
c:=c+c div 10;
c:=c mod 10;
end;
len:=a[0]+b[0]+4;
while c[len]=0 do dec(len);
if len>500 then c[0]:=500 else c[0]:=len;
end;
procedure work;
var
i,j,k:longint;
begin
a[0]:=1;a[1]:=1;b[0]:=1;b[1]:=2;
for i:=c[0] downto 1 do
if c[i]=0 then chen(a,a,a)
else begin chen(a,a,a);chen(a,b,a) end;
end;
procedure ci;
var
i,j:longint;
begin
i:=n;j:=1;
while i>0 do
begin
c[j]:=i mod 2;
i:=i div 2;
inc(j);
end;
c[0]:=j-1;
end;
procedure print;
var
i,j,k:longint;
begin
writeln(trunc(n*(ln(2)/ln(10)))+1);
j:=1;k:=1;
a[1]:=a[1]-1;
for i:=500 downto 1 do
begin
if (j mod 50=1) and (j1) then writeln;
write(a[i]);
inc(j);
end;
end;
begin
readln(n);
ci;
work;
print;
end.
秒杀，一次ac -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
我用的是倍增思想。
减少高精乘的次数。 -
0
czz5242199 LV 9 @ 2008-11-06 18:17:11
通过这个题目，我学会了二分法快速求幂！！
var a,t:array[0..600] of word;
p:longint;
procedure main1;
var k:extended;
begin
k:=Ln(2)/Ln(10);
writeln(trunc(p*k)+1);
end;
procedure cheng2;
var i,k:longint;
begin
for i:=1 to 500 do
a[i]:=a[i]*2;
for i:=1 to 500 do
begin
inc(a,a[i] div 10);
a[i]:=a[i] mod 10;
end;
end;
procedure chengcheng;
var i,k,j:longint;
begin
t:=a; fillchar(a,sizeof(a),0);
for i:=1 to 500 do
for k:=1 to 500-i+1 do
begin
inc(a,t[i]*t[k]);
inc(a,a div 10);
a:=a mod 10;
end;
end;
procedure try(p:longint);
var mid:longint;
begin
if p=1 then
begin
cheng2; exit;
end;
if odd(p) then
begin
mid:=p div 2;
try(mid); chengcheng; cheng2;
exit;
end;
mid:=p div 2;
try(mid);
chengcheng;
end;
procedure main2;
var i:longint;
begin
a[1]:=1;
try(p);
dec(a[1]);
for i:=500 downto 1 do
begin
write(a[i]);
if i mod 50=1 then writeln;
end;
end;
begin
readln(p);
main1;
main2;
end. -
0
jtjxhjl321 LV 3 @ 2008-11-05 16:12:47
编译通过...
├ 测试数据 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) (1)
再对结果(1)求出平方，即双高精，规模 大欧(250000) (2)
如果n为奇再对得到的结果(2)加倍，即高精加，或单高精乘，规模 大欧(500)
最坏情况的规模 大欧(n) -
0
windytalker LV 3 @ 2008-11-05 16:26:31
program mai;
var int,out:array[1..1000] of longint;
p,n,m,i,j:integer;
procedure solve(n:integer);
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
int:=int+out[i]*out[j]
else
int:=int+out[i]*out[j]*2;
for i:= 1 to 10000 do
begin
out[i]:=int[i] mod 10;
int:=int+int[i] div 10;
end;
for i:= 1 to 1000 do
int[i]:=0;
end;
begin
read(p); out[1]:=1;
writeln(trunc(p*ln(2)/ln(10))+1);
solve(p);
j:=0;
for i:=500 downto 2 do
begin
write(out[i]);
j:=j+1;
if j mod 50 =0 then writeln;
end;
write(out[1]-1);
end. -
0
编译通过...
├ 测试数据 01：运行超时...
├ 测试数据 02：运行超时...
├ 测试数据 03：答案正确... 243ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：运行超时...
├ 测试数据 10：运行超时...
---|---|---|---|---|---|---|---|-
Unaccepted 有效得分：60 有效耗时：243ms
var
a:array[1..105]of longint;
p,n,i,j,k,wei,jin,q:longint;
begin
readln(p);
wei:=trunc(p*ln(2)/ln(10))+1;
writeln(wei);
fillchar(a,sizeof(a),0);
a[1]:=2;k:=1;
jin:=0;
for i:=1 to p-1 do
begin
for j:=1 to k do
a[j]:=a[j]*2;
for j:=1 to k do
begin
jin:=a[j] div 100000;
a[j]:=a[j]mod 100000;
a[j+1]:=a[j+1]+jin;
end;
if (jin>0)and(k -
0
├ 测试数据 01：运行时错误...|错误号: -1073741819
├ 测试数据 02：运行时错误...|错误号: -1073741819
├ 测试数据 03：运行时错误...|错误号: -1073741819
├ 测试数据 04：运行时错误...|错误号: -1073741819
├ 测试数据 05：运行时错误...|错误号: -1073741819
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：运行时错误...|错误号: -1073741819
├ 测试数据 10：运行时错误...|错误号: -1073741819
---|---|---|---|---|---|---|---|-
Unaccepted 有效得分：30 有效耗时：0ms
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|-
#include
int a[501]={0};
main (){
//freopen ("P1223.in","r",stdin);
//freopen ("P1223.out","w",stdout);
int p,i,j,k,t,l;
scanf ("%d",&p);
a[1]=1;
t=1;
for (i=1;i -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms一次ac
用分治
2^n=(2^(n div 2))^2*2^(n mod 2)program vijos_p1223;
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
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
再强大的压位高精也不如二分法猛啊。
去年noip就栽在二分法上了 -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-Accepted 有效得分：100 有效耗时：0ms
位数直接用 [x*lg(2)]+1 就可以算出来了，接下来后500位高精度，用2维数组记录2^(2^n)后500位，用空间换时间
victorygod
LV 5
@ 2009-02-13 11:18:37
