154 条题解
-
0
q3w4w5 LV 8 @ 2014-07-29 10:01:08
#include<iostream>
#include<cmath>
using namespace std;
const unsigned int MAX = 1000;
const long long WIDTHMAX = 100000;
const unsigned int WIDTH = 5;
typedef struct node
{
long long val[MAX];
unsigned int size;
} BigInt;
void PrintBigInt(BigInt a);
BigInt MulBigInt(const BigInt & a, const BigInt & b);
void PowBigInt(BigInt & c, unsigned int n);
int main()
{
unsigned int p;
cin >> p;
cout << int(log10(2)*p) + 1 << endl;
BigInt a;
PowBigInt(a, p);
a.val[0] -= 1;
PrintBigInt(a);
system("pause");
return 0;
}void PowBigInt(BigInt & c, unsigned int n)
{
int stack[MAX] = {0};
int top = 0;
while (n > 0)
{
stack[top++] = n % 2;
n /= 2;
}
BigInt b;
b.size = 1;
b.val[0] = 2;
c.size = 1;
c.val[0] = 1;
for (int i=top-1; i>=0; i--)
{
c = MulBigInt(c, c);
if (stack[i] == 1)
c = MulBigInt(b, c);
}
}
void PrintBigInt(BigInt a)
{
while (a.size*WIDTH < 500)
{
a.val[a.size++] = 0;
}
while (a.size*WIDTH > 500)
{a.size--;
}
for (int i=a.size-1; i>=0; i--)
{
if (a.val[i] < 10)
cout << "0000";
else if (a.val[i] < 100)
cout << "000";
else if (a.val[i] < 1000)
cout << "00";
else if (a.val[i] < 10000)
cout << "0";
cout << a.val[i];
if (i % 10 == 0)
cout << endl;
}
}
BigInt MulBigInt(const BigInt & a, const BigInt & b)
{
if (a.size == 1 && a.val[0] == 0)
return a;
if (b.size == 1 && b.val[0] == 0)
return b;
const int LEN = 500 / WIDTH + 1;
BigInt c;
for (int i=0; i<MAX; i++)
c.val[i] = 0;
for (int i=0, j=0; i<b.size && i<LEN; i++)
{
for (j=0; j<a.size && j<LEN; j++)
{
c.val[i+j] += a.val[j] * b.val[i];
c.val[i+j+1] += c.val[i+j] / WIDTHMAX;
c.val[i+j] %= WIDTHMAX;
}
c.size = i + j;if (c.val[c.size] != 0)
c.size++;}
return c;}
-
0
###Block code
/*happywu
* 2014.7.5
* vojos 1223
*/
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
int a[600],b[600],c[1200],ans[600];
ll p;
void mul(int *a,int *b)
{
memset(c,0,sizeof(c));
for(int i=1;i<=500;i++)
for(int j=1;j<=500;j++)
{
c[i+j-1]+=a[i]*b[j]%10;
c[i+j]+=a[i]*b[j]/10;
}
for(int i=1;i<=500;i++)
{
c[i+1]+=c[i]/10;
c[i]=c[i]%10;
}
for(int i=1;i<=500;i++)
a[i]=c[i];
}
void quick_power()
{
ans[1]=1;
a[1]=2;
while(p)
{
if(p&1)mul(ans,a);
mul(a,a);
p>>=1;
}
}
void subtract()
{
if(ans[1]>=1)
{
ans[1]--;
return;
}
int i=1;
ans[i]--;
while(ans[i]<0 && i<=501)
{
ans[i]=9;
ans[i+1]--;
i++;
}
}
int main()
{
cin>>p;
int wei=p*log10(2)+1;
cout<<wei<<endl;
quick_power();
subtract();
for(int i=500;i>=1;i--)
{
printf("%d",ans[i]);
if((i-1)%50==0)printf("\n");
}
return 0;
} -
0
lingmingxiao2002 LV 8 @ 2014-04-20 16:23:31
#include <iostream>
#include <math.h>
#include <algorithm>
#include <stdio.h>
#include <string.h>
using namespace std;
int a[10000],ans[10000],c[10000];
int p,n;void pingfang(int a[],int b[])
{
int i,j,k;
k=0;
memset(c,0,sizeof(c));
for (i=0;i<500;i++)
for (j=0; j<500-i+1;j++){
c[i+j]+=a[i]*b[j];
k= c[i+j] / 10;
c[i+j+1]=c[i+j+1]+k;
c[i+j] %= 10;
}
for (i=0;i<500;i++) a[i]=c[i];
}
int main()
{
cin>>p;
cout<<int (p*log10(2)+1)<<endl;
memset(ans,0,sizeof(ans));
memset(a,0,sizeof(a));
a[0]=2;
ans[0]=1;
while (p>0) {
if (p % 2==1) pingfang(ans,a);
p /=2;
pingfang(a,a);
}
ans[0]--;
for (int i=499;i>=0;i--){
cout<<ans[i];
if (i % 50==0) cout<<endl;
}
system("pause");
return 0;
}
#include <iostream>
#include <math.h>
#include <algorithm>
#include <stdio.h>
#include <string.h>
using namespace std;
int a[10000],ans[10000],c[10000];
int p,n;void pingfang(int a[],int b[])
{
int i,j,k;
k=0;
memset(c,0,sizeof(c));
for (i=0;i<500;i++)
for (j=0; j<500-i+1;j++){
c[i+j]+=a[i]*b[j];
k= c[i+j] / 10;
c[i+j+1]=c[i+j+1]+k;
c[i+j] %= 10;
}
for (i=0;i<500;i++) a[i]=c[i];
}
int main()
{
cin>>p;
cout<<int (p*log10(2)+1)<<endl;
memset(ans,0,sizeof(ans));
memset(a,0,sizeof(a));
a[0]=2;
ans[0]=1;
while (p>0) {
if (p % 2==1) pingfang(ans,a);
p /=2;
pingfang(a,a);
}
ans[0]--;
for (int i=499;i>=0;i--){
cout<<ans[i];
if (i % 50==0) cout<<endl;
}
system("pause");
return 0;
}
#include <iostream>
#include <math.h>
#include <algorithm>
#include <stdio.h>
#include <string.h>
using namespace std;
int a[10000],ans[10000],c[10000];
int p,n;void pingfang(int a[],int b[])
{
int i,j,k;
k=0;
memset(c,0,sizeof(c));
for (i=0;i<500;i++)
for (j=0; j<500-i+1;j++){
c[i+j]+=a[i]*b[j];
k= c[i+j] / 10;
c[i+j+1]=c[i+j+1]+k;
c[i+j] %= 10;
}
for (i=0;i<500;i++) a[i]=c[i];
}
int main()
{
cin>>p;
cout<<int (p*log10(2)+1)<<endl;
memset(ans,0,sizeof(ans));
memset(a,0,sizeof(a));
a[0]=2;
ans[0]=1;
while (p>0) {
if (p % 2==1) pingfang(ans,a);
p /=2;
pingfang(a,a);
}
ans[0]--;
for (int i=499;i>=0;i--){
cout<<ans[i];
if (i % 50==0) cout<<endl;
}
system("pause");
return 0;
} -
0
program mason;
var n:array[1..500] of integer;
i,j,k,s,m:longint;
p,p0:longint;
begin
assign(input,'mason.in');
reset(input);
assign(output,'mason.out');
rewrite(output);
read(p);
writeln(trunc((p*ln(2))/ln(10)+1));
for i:=1 to 500 do n[i]:=0;
n[1]:=1;
m:=1;
for i:=1 to 26 do m:=m*2;
p0:=p mod 26;
p:=p div 26;
for i:=1 to p do
begin
k:=0;
for j:=1 to 500 do
begin
s:=n[j]*m+k;
k:=s div 10;
n[j]:=s mod 10
end;
end;
for i:=1 to p0 do
begin
k:=0;
for j:=1 to 500 do
begin
s:=n[j]*2+k;
k:=s div 10;
n[j]:=s mod 10;
end;
end;
n[1]:=n[1]-1;
for i:=9 downto 0 do
begin
for j:=50 downto 1 do write(n[i*50+j]);
writeln;
end;
close(input);
close(output);
end. -
0
ChinaLover LV 7 @ 2013-08-27 23:13:23
明天写 快速幂+高精度
爷明天来搞你！！ -
0
从0分到10分，我无奈了
-
0
我就留个念...肯定还有更好的写法.
import java.text.DecimalFormat;
import java.util.Scanner;
import java.math.BigInteger;
public class Main {
static Scanner cin=new Scanner(System.in);
static int n;
static BigInteger res=BigInteger.valueOf(2);
static BigInteger tmod=BigInteger.valueOf(10);
public static void main(String args[])
{
n=cin.nextInt();
tmod=tmod.pow(500);
res=res.modPow(BigInteger.valueOf(n), tmod).subtract(BigInteger.ONE).add(tmod);
System.out.println((int)(n*Math.log10(2)+1));
DecimalFormat DemicalTest=new DecimalFormat("00000000000000000000000000000000000000000000000000,00000000000000000000000000000000000000000000000000");
String sres=DemicalTest.format(res);
sres=sres.replace(',','\n');
System.out.println(sres.substring(2));}
} -
0
把取整trunc 记成 round~
type
cc=array[0..520]of longint;
var
ans:Longint;
i,j,k,x,m,l,n,p:longint;
a,b,c:cc;
procedure plus(var a:cc;b:cc);
begin
fillchar(c,sizeof(c),0);
n:=a[0];
m:=b[0];
for i:=1 to n do
begin
x:=0;
for j:=1 to m do
begin
if i+j-1>510 then break;
c[i+j-1]:=c[i+j-1]+a[i]*b[j]+x;
x:=c[i+j-1]div 10;
c[i+j-1]:=c[i+j-1] mod 10;
end;
if x<>0 then c[i+j]:=x;
end;
n:=i+j-1;
if n>510 then n:=510;
if (c[n+1]<>0)and(n<510) then inc(n);
a:=c;
a[0]:=n;
end;
begin
read(p);
writeln(trunc(p*ln(2)/ln(10))+1);
n:=1;
m:=0;
a[1]:=2;
a[0]:=1;
b[1]:=1;
b[0]:=1;
while p>0 do
begin
if p and 1=1 then
plus(b,a);
plus(a,a);
p:=p shr 1;
end;
j:=0;
dec(b[1]);
for i:=500 downto 1 do
begin
inc(j);
write(b[i]);
if j mod 50=0 then writeln;
end;
end. -
0
一样的程序 一样的测评机 结果如下 第一次：
VijosNT Mini 2.0.5.7 Special for Vijos
编译通过...
├ 测试数据 01：答案正确... (793ms, 584KB)
├ 测试数据 02：答案正确... (0ms, 584KB)
├ 测试数据 03：答案正确... (0ms, 584KB)
├ 测试数据 04：答案正确... (0ms, 584KB)
├ 测试数据 05：答案正确... (0ms, 584KB)
├ 测试数据 06：答案正确... (0ms, 584KB)
├ 测试数据 07：答案正确... (0ms, 584KB)
├ 测试数据 08：答案正确... (0ms, 584KB)
├ 测试数据 09：答案正确... (0ms, 584KB)
├ 测试数据 10：运行超时... (?, 512KB)---|---|---|---|---|---|---|---|-
Unaccepted / 90 / ? / 584KB第二次：
VijosNT Mini 2.0.5.7 Special for Vijos
编译通过...
├ 测试数据 01：答案正确... (0ms, 584KB)
├ 测试数据 02：答案正确... (0ms, 584KB)
├ 测试数据 03：答案正确... (0ms, 584KB)
├ 测试数据 04：答案正确... (0ms, 584KB)
├ 测试数据 05：答案正确... (0ms, 584KB)
├ 测试数据 06：答案正确... (0ms, 584KB)
├ 测试数据 07：答案正确... (0ms, 584KB)
├ 测试数据 08：答案正确... (0ms, 584KB)
├ 测试数据 09：答案正确... (0ms, 584KB)
├ 测试数据 10：答案正确... (0ms, 584KB)---|---|---|---|---|---|---|---|-
Accepted / 100 / 0ms / 584KBvijos又抽了吗？？？？
-
0
Jinpeng1998 LV 7 @ 2012-08-08 17:33:57
program ngfjbfjbg;
type arr=array[1..500]of longint;
var n,p,i,j:longint;
ans,num:arr;
function mul(a,b:arr):arr;
var i,j:longint;
c:arr;
begin
for i:=1 to 500 do c[i]:=0;
for i:=1 to 500 do
for j:=1 to 500-i+1 do
c:=c+a[i]*b[j];
for i:=1 to 499 do begin
c:=c+c[i] div 10;
c[i]:=c[i] mod 10;
end;
c[500]:=c[500] mod 10;
mul:=c;
end;
begin
read(p);
n:=p;
ans[1]:=1; num[1]:=2;
while p>0 do begin
if p mod 2=1 then ans:=mul(ans,num);
p:=p div 2;
num:=mul(num,num);
end;
writeln(trunc(n*ln(2)/ln(10))+1);
dec(ans[1]); p:=1;
for i:=500 downto 1 do
begin
if p=50 then begin writeln(ans[i]);p:=1;end
else begin write(ans[i]); inc(p); end;
end;
end. -
0
问题一：求位数。由求指数公式我们可知2^p-1的位数为log(10)/log(2)*p+1，但是由于pascal语言中没有log函数，所以我们可以将其写成p*ln(2)/ln(10)+1。
问题二：2^p的运算。我们可以采用二分法来解决这个问题，如果已知2^(p/2)我们只需将它在自乘以便就可以得到2^p。这样就省去了一半的运算量。由此我们可到函数mul(p,ans)
Function mul(p)
if p=1
then mul ->2
else
T ->mul(p div 2)
mul ->t*t
if p mod 2=1 then mul ->mul*2
这样算法的时间复杂度就为log(n)*高精度乘法的时间。
但是如果本题用递归来写的话，因为高精度数字所占内存太大，这样很有可能在建栈的时候内存溢出，所以我们要把递归写成递推，观察每次迭代的p的变化，我们将其写成如下形式：
t ->2
n ->1
while p0
if p为奇数 then n ->n*t
t ->t*t
p ->p div 2
至于高精度乘法是一个基础问题，这里不再累述。源程序详见我的博客上的日志http://zhurui250.blog.163.com/blog/static/137270520201001693543791/
-
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
我SB啊
算500位就可以了我全算出来
结果TLE -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0msAC！
二分快速幂+高精~~~~晒晒程序
Var
a,b:array [0..1001] of Longint;
n,i,j:Longint;Procedure quick(k:Longint);
Var
i,c,j,l:Longint;
Begin
If k=0 Then Exit;
quick(k div 2);
If k mod 20 Then c:=2 Else c:=1;
For l:=1 to 500 Do
For i:=1 to 500 Do Inc(b,a[i]*a[l]*c);
For i:=1 to 500 Do Begin
b:=b+b[i] div 10;
b[i]:=b[i] mod 10;
End;
a:=b;
Fillchar(b,sizeof(b),0);
End;Begin
Readln(n);
Writeln(trunc(ln(2)/ln(10)*n)+1);
a[1]:=1;
quick(n);
Dec(a[1]);
For i:=500 downto 2 Do Begin
Write(a[i]);
If i mod 50=1 Then Writeln;
End;
Writeln(a[1]);
Readln;
End. -
0
xiaoxiao-tg LV 7 @ 2009-11-08 09:09:16
快速幂的循环次数一直搞错了 最后才写成递归
const maxn=1000000;
type arr=array[0..maxn] of integer;
var c,now,ss:arr;
p,num,i,j:longint;
procedure init;
begin
readln(p);
ss[0]:=1;
ss[1]:=2;
end;
procedure add(var ans,a,b:arr);
var i,j,k:longint;
max:integer;
begin
fillchar(ans,sizeof(ans),0);
for i:=1 to a[0] do
for j:=1 to b[0] do
inc(ans,a[i]*b[j]);
max:=a[0]+b[0];
for i:=1 to max-1 do
begin
inc(ans,ans[i] div 10);
ans[i]:=ans[i] mod 10;
end;
k:=max;;
while (ans[k]=0)and(k>1)do
dec(k);
if k>500
then k:=500;
ans[0]:=k;
end;
procedure swap;
var i:longint;
begin
for i:=0 to now[0] do
c[i]:=now[i];
end;
procedure work(num:longint);
var i,j:longint;
begin
if num -
0
var n,l,p,len,i:longint;
a,b:array[1..2000]of longint;procedure doit(p:longint);
var i1,i2,i3:longint;
begin
if p=0 then exit;
doit(p div 2);
if odd(p) then p:=2 else p:=1;
fillchar(b,sizeof(b),0);
for i1:=1 to 500 do
for i2:=1 to 500 do
begin
b[i1+i2-1]:=b[i1+i2-1]+a[i2]*a[i1]*p;
if b[i1+i2-1]>=10 then
begin
b[i1+i2]:=b[i1+i2]+b[i1+i2-1] div 10;
b[i1+i2-1]:=b[i1+i2-1] mod 10;
end;
end;
a:=b;
end;begin
read(n);
l:=trunc(ln(2)/ln(10)*n)+1;
a[1]:=1;
doit(n);
writeln(l);
a[1]:=a[1]-1;
for i:=500 downto 1 do
begin
write(a[i]);
if (i-1) mod 50=0 then writeln;
end;
end. -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|--
Accepted 有效得分：100 有效耗时：0msprogram ex;
var n:longint;
i,j:longint;
out:array[1..500] of longint;
sta:array[1..1000] of longint;
procedure solve(n:longint);
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
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);
out[1]:=1;
solve(n);
for i:=500 downto 2 do
begin
write(out[i]);
if i mod 20=1 then writeln;
end;
writeln(out[1]-1);
end. -
0
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)
q3w4w5
LV 8
@ 2014-07-29 10:01:08
