Tag Archives: 高精度

ZOJ 2529(不同进制的高精度&sstream）

Posted on by

高精度 a+b

第i位的进制为第 ith 系数

慢慢做吧……

Important---：切记质数表一定要开大一些

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<cctype>
#include<iostream>
#include<functional>
#include<algorithm>
#include<sstream>
using namespace std;
int a[100],siz=0;
char a1[1000],a2[1000];
int A[1000],B[1000],C[1000];
void stod()
{

	istringstream ss(a1);
	int i=1;
	while (ss)
	{
		ss>>A[i];
		i++;
		char c;
		if (ss) ss>>c;
	}
	A[0]=i-1;
	stringstream ss2;
	ss2<<a2;
	i=1;
	while (ss2)
	{
		ss2>>B[i];
		i++;
		char c;
		if (ss2) ss2>>c;
	}
	B[0]=i-1;
	for (int i=1;i<=(A[0]>>1);i++) swap(A[i],A[A[0]-i+1]);
	for (int i=1;i<=(B[0]>>1);i++) swap(B[i],B[B[0]-i+1]);

}
int main()
{
	for (int i=1;siz<=80;i++)
	{
		bool flag=0;
		for (int j=2;j<=i-1;j++)
			if (i%j==0) flag=1;
		if (!flag)
		{
			siz++;
			a[siz]=i;
		}
	}
//	for (int i=1;i<=25;i++) cout<<a[i]<<' ';
	while (scanf("%s%s",a1,a2)!=EOF)
	{
		memset(A,0,sizeof(A));
		memset(B,0,sizeof(B));
		stod();
//		for (int i=1;i<=B[0];i++) cout<<B[i]<<' ';
		memset(C,0,sizeof(C));
		C[0]=max(A[0],B[0])+1;
		for (int i=1;i<=C[0];i++)
		{
			C[i]+=A[i]+B[i];
			C[i+1]+=C[i]/a[i+1];
			C[i]%=a[i+1];
		}
		while (!C[C[0]]) C[0]--;
		for (int i=C[0];i>=2;i--) cout<<C[i]<<",";
		cout<<C[1]<<endl;
	}
//	while (1);
	return 0;
}

POJ 3289(高精度乘法）

Posted on by

高精度乘法

Program P3289;
const
   maxn=40000;
   F=10;
type
   arr=record
       d:array[1..maxn] of longint;
       len,doc:longint;
       end;
var
   r,m:arr;
   y:longint;
   i:longint;
   a,b:arr;
function max(a,b:longint):longint;
begin
   if a<b then exit(b) else exit(a);
end;
procedure multipy(a,b:arr;var c:arr);
var
   i,j,len:longint;
begin
   fillchar(c,sizeof(c),0);
   c.len:=a.len+b.len;

   for i:=1 to a.len do
      for j:=1 to b.len do
      begin
         inc(c.d[i+j-1],a.d[i]*b.d[j]);
         inc(c.d[i+j],c.d[i+j-1] div F);
         c.d[i+j-1]:=c.d[i+j-1] mod F;
      end;
   while (c.d[c.len]=0) and (c.len>1) do dec(c.len);
   c.doc:=a.doc+b.doc;


end;
procedure to_arr(doc:longint;var c:arr);
var
   x,i,n:longint;
begin
   read(x);
   i:=0;
   while (x>0) do
   begin
      inc(i);
      c.d[i]:=x mod F;
      x:=x div F;
   end;
   c.len:=i;
   c.doc:=doc;
end;
Procedure jie(a:arr;x:longint;var c:arr);
begin
   if x=1 then begin c:=a; exit; end;
   fillchar(c,sizeof(c),0);
   if (x mod 2=0) then
   begin
      jie(a,x div 2,c);
      multipy(c,c,c);
   end
   else
   begin
      jie(a,x div 2,c);
      multipy(c,c,c);
      multipy(a,c,c);
   end;
end;
begin
   to_arr(2,r);
   r.len:=3;r.d[3]:=1;
   to_arr(0,m);
   read(y);
   jie(r,y,r);
   multipy(m,r,m);


   for i:=m.len downto m.doc+1 do write(m.d[i]);
   writeln;

end.

POJ 2390 (小数高精度乘法）

Posted on by

小数高精度乘法

m*(1+r/100)^y

Program P2390;
const
   maxn=40000;
   F=10;
type
   arr=record
       d:array[1..maxn] of longint;
       len,doc:longint;
       end;
var
   r,m:arr;
   y:longint;
   i:longint;
   a,b:arr;
function max(a,b:longint):longint;
begin
   if a<b then exit(b) else exit(a);
end;
procedure multipy(a,b:arr;var c:arr);
var
   i,j,len:longint;
begin
   fillchar(c,sizeof(c),0);
   c.len:=a.len+b.len;

   for i:=1 to a.len do
      for j:=1 to b.len do
      begin
         inc(c.d[i+j-1],a.d[i]*b.d[j]);
         inc(c.d[i+j],c.d[i+j-1] div F);
         c.d[i+j-1]:=c.d[i+j-1] mod F;
      end;
   while (c.d[c.len]=0) and (c.len>1) do dec(c.len);
   c.doc:=a.doc+b.doc;


end;
procedure to_arr(doc:longint;var c:arr);
var
   x,i,n:longint;
begin
   read(x);
   i:=0;
   while (x>0) do
   begin
      inc(i);
      c.d[i]:=x mod F;
      x:=x div F;
   end;
   c.len:=i;
   c.doc:=doc;
end;
Procedure jie(a:arr;x:longint;var c:arr);
begin
   if x=1 then begin c:=a; exit; end;
   fillchar(c,sizeof(c),0);
   if (x mod 2=0) then
   begin
      jie(a,x div 2,c);
      multipy(c,c,c);
   end
   else
   begin
      jie(a,x div 2,c);
      multipy(c,c,c);
      multipy(a,c,c);
   end;
end;
begin
   to_arr(2,r);
   r.len:=3;r.d[3]:=1;
   to_arr(0,m);
   read(y);
   jie(r,y,r);
   multipy(m,r,m);


   for i:=m.len downto m.doc+1 do write(m.d[i]);
   writeln;

end.

RQNOJ 38(串的计数）

Posted on by

一个长度为3N字符串满足：由N个A，N个B，N个C组成，对于它的任意前缀，满足A的个数>=B的个数>=C的个数。求满足这样条件的字符串的个数。


看到这题第一反应：打表！第二反应三个字：高精度

这题动态转移方程为f[i,j,k]=f[i-1,j,k]+f[i,j-1,k]+f[i,j,k-1]  i,j,k表示A,B,C的个数，考察是否可行

高精啊高精……

Program str;
type
   arr=record
           len:longint;
           d:array[1..15] of longint;
       end;
var
   n,i,j,k:longint;
   f:array[0..60,0..60,0..60] of arr;
function max(a,b:longint):longint;
begin
   if a>b then exit(a) else exit(b);
end;
procedure sum(a,b:arr;var c:arr);
var
   i,j:longint;
const
   F=100000000;

begin
   fillchar(c,sizeof(c),0);
   c.len:=max(a.len,b.len);
   for i:=1 to c.len do
   begin
      inc(c.d[i],a.d[i]+b.d[i]);
      inc(c.d[i+1],c.d[i] div F);
      c.d[i]:=c.d[i] mod F;
   end;
   if c.d[c.len+1]>0 then inc(c.len);

   while (c.len>0) and (c.d[c.len]=0) do dec(c.len);


end;
Procedure print(a:arr);
var
   i,p:longint;
begin
   write(a.d[a.len]);
   for i:=a.len-1 downto 1 do
   begin
      p:=a.d[i];
      if p<10000000 then write('0');
      if p<1000000 then write('0');
      if p<100000 then write('0');
      if p<10000 then write('0');
      if p<1000 then write('0');
      if p<100 then write('0');
      if p<10 then write('0');
      write(p);
   end;
   writeln;
end;
begin
   read(n);
   fillchar(f,sizeof(f),0);
   f[0,0,0].len:=1;
   f[0,0,0].d[1]:=1;
   for i:=1 to n do
      for j:=0 to i do
         for k:=0 to j do
         begin
            if k>0 then
            begin
               sum(f[i,j,k],f[i,j,k-1],f[i,j,k]);
            end;
            if i>j then sum(f[i,j,k],f[i-1,j,k],f[i,j,k]);
            if j>k then sum(f[i,j,k],f[i,j-1,k],f[i,j,k]);
         end;

   print(f[n,n,n]);
end.

POJ 2084 (Catalan数)

Posted on by

卡特兰数三大公式

C(n)=C(n-1)*(4*n-2)/(n+1)

C(n)=C(2n-1,n+1)-C(2n-1,n-1)

C(n)=C(2n,n)/(n+1)

Program p2084;
Const
   F=10000;
Type
   arr=record
       a:array[1..10000] of longint;
       len:longint;
       end;
var
   n,i,j:longint;
   c:array[1..101] of arr;
Procedure Mulpily(a:arr;b:longint;var c:arr);
var
   i,j:longint;
begin
   fillchar(c,sizeof(c),0);
   for i:=1 to a.len do
   begin
      inc(c.a[i],a.a[i]*b);
      inc(c.a[i+1],c.a[i] div F);
      c.a[i]:=c.a[i] mod F;
   end;
   c.len:=a.len;
   while c.a[c.len+1]>0 do
   begin
      inc(c.len);
      inc(c.a[c.len+1],c.a[c.len] div F);
      c.a[c.len]:=c.a[c.len] mod F;
   end;
   while (c.len>1) and (c.a[c.len]=0) do dec(c.len);

end;
Procedure Divede(a:arr;b:longint;var c:arr);
var
   i,j,d:longint;
begin
   fillchar(c,sizeof(c),0);
   d:=0;
   for i:=a.len downto 1 do
   begin
      d:=d*F+a.a[i];
      c.a[i]:=d div b;
      d:=d mod b;
   end;
   c.len:=a.len;
   while (c.len>1) and (c.a[c.len]=0) do dec(c.len);

end;
Procedure prin(a:arr);
var
   i,j:longint;
begin
   write(a.a[a.len]);
   for i:=a.len-1 downto 1 do
   begin
      if a.a[i]<1000 then write('0');
      if a.a[i]<100 then write('0');
      if a.a[i]<10 then write('0');
      write(a.a[i]);
   end;
   writeln;
end;
begin
   fillchar(c,sizeof(c),0);
   c[1].len:=1;
   c[1].a[1]:=1;
   c[2].len:=1;
   c[2].a[1]:=1;
   for i:=3 to 101 do
   begin
      Mulpily(c[i-1],4*i-2,c[i]);
      divede(c[i],i+1,c[i]);
   end;
   read(n);
   while (n<>-1) do
   begin
      prin(c[n+1]);
      read(n);
   end;

end.

POJ 1001 (坑爹的小数高精度乘法)

Posted on by

小数高精度乘法

program P1001;
Type
    arr=record
        a:array[1..10000] of longint;
        len:longint;
        xs:longint;
        end;
Var
    s:ansistring;
    n,i,j,k,len:longint;
    r:arr;
Procedure relax(var c:arr);
var
   i,j:longint;
begin
   while (c.a[c.len]=0) and (c.len>1) do dec(c.len);
   if (c.len=1) and (c.a[1]=0) then begin c.xs:=0; exit; end;
   i:=1;
   while (c.a[i]=0) do inc(i);
   dec(i);
   if (i>0) then
   begin
      if (c.xs>=i) then dec(c.xs,i)
      else
      begin
         i:=c.xs;
         c.xs:=0;
      end;
      for j:=i+1 to c.len do c.a[j-i]:=c.a[j];
      dec(c.len,i);
   end;
end;
procedure prin(c:arr);
var
   i:longint;
begin
   relax(c);
   if (c.xs=0) then
   begin
      for i:=c.len downto 1 do write(c.a[i]);
      writeln;
      exit;
   end;
   if (c.xs<=c.len) then
   begin
      for i:=c.len downto c.xs+1 do write(c.a[i]);
      write('.');
      for i:=c.xs downto 1 do write(c.a[i]);
      writeln;
      exit;
   end;
   write('.');
   for i:=1 to c.xs-c.len do write('0');
   for i:=c.len downto 1 do write(c.a[i]);
   writeln;
end;
Procedure cheng(a:arr;b:arr;var c:arr);
var
   i,j:longint;
begin
   fillchar(c,sizeof(c),0);
   for i:=1 to a.len do
      for j:=1 to b.len do
      begin
         inc(c.a[i+j-1],a.a[i]*b.a[j]);
         inc(c.a[i+j],c.a[i+j-1] div 10);
         c.a[i+j-1]:=c.a[i+j-1] mod 10;
      end;
   c.len:=a.len+b.len+1;
   c.xs:=a.xs+b.xs;

   relax(c);

end;
procedure jie(a:arr;b:longint;var c:arr);
begin
   if (b=1) then c:=a
   else if (b mod 2=0) then
   begin
      jie(a,b div 2,c);
      cheng(c,c,c);
   end
   else begin
      jie(a,b div 2,c);
      cheng(c,c,c);
      cheng(c,a,c);
   end;

end;
Begin
   while (not(eof)) do
   begin
      readln(s);
      len:=length(s);
      i:=pos(' ',s);
      j:=pos('.',s);
      if j=0 then
      begin
         r.xs:=0;
         r.len:=i-1;
         for k:=1 to r.len do r.a[r.len-k+1]:=ord(s[k])-48;
      end
      else begin
      r.xs:=i-j-1;
      r.len:=i-2;
      for k:=1 to j-1 do r.a[r.len-k+1]:=ord(s[k])-48;
      for k:=j+1 to i-1 do r.a[r.len-k+2]:=ord(s[k])-48;
      end;
      relax(r);
      i:=len;
      while (s[i]<>' ') do dec(i);
      n:=0;
      for k:=i+1 to len do n:=n*10+ord(s[k])-48;
      jie(r,n,r);
      prin(r);
  end;
end.