Класс Elm

public class elm implements java.io.Serializable

{

object obj;

elm next, prev;

public elm( )

{

obj=null;

next=prev=this;

}

public elm(object val)

{

obj=val;

next=prev=this;

}

public void remove()

{

prev.next=next;

next.prev=prev;

next=prev=null;

}

void after(object val)

{

elm tmp=next;

next=new elm(val);

next.prev=this;

next.next=tmp;

next.next.prev=next;

}

void before(object val)

{

elm tmp=prev;

prev=new elm(val);

prev.next=this;

prev.prev=tmp;

prev.prev.next=prev;

}

String put()

{

return obj.Put();

}

}

Класс BigInt

import java.io.*;

public class BigInt implements object, java.io.Serializable

{

int sz; // тек. размер

byte[] pd; //адрес памяти

int max(int val1,int val2)

{

return (val1 > val2) ? val1 : val2;

}

///////////////////////////////////////////////////////////////////////////

public int Get(String s) // Загрузка из текстовой строки (внешняя форма)

{

In(s);

return 1;

}

public String Put() // Сохранение в текстовой строке (динамический массив)

{

return Out();

}

public int Load(InputStream I) throws Exception // Загрузка из символьного потока

{

integer sz_n=new integer(0);

sz_n.Load(I);

sz=sz_n.val;

pd=new byte[sz];

I.read(pd);

return 1;

}

public void Save(OutputStream O) throws Exception // Сохранение в символьный поток

{

integer sz_n=new integer(sz);

sz_n.Save(O);

O.write(pd);

}

public void BLoad(FileInputStream I) throws IOException, ClassNotFoundException // Загрузка из двоичного потока

{

ObjectInputStream ois = new ObjectInputStream(I);

Object objRead;

objRead = ois.readObject();

BigInt tmp=(BigInt)objRead;

sz = tmp.sz;

pd=tmp.pd;

}

public void BSave(OutputStream O) throws IOException // Сохранение в двоичного поток

{

Object objSave = this;

ObjectOutputStream oos = new ObjectOutputStream(O);

oos.writeObject(objSave);

}

public int Type(){ return 3;} // Возвращение идентификатора класса

public String Name(){ return "BigInt"; }// Возвращение имени класса

public int Cmp(object q) // Сравнение объектов класса

{

if (Type()!=q.Type()) return Type()-q.Type();

BigInt out = new BigInt(this);

out.sub((BigInt)q);

int i;

for (i=0;i<out.sz && out.pd[i]==0;i++);

if (i==out.sz) return 0;

if ((out.pd[out.sz-1] & 0x80) !=0)

return -1;

return 1;

// String str_out=new String(out.Out());

// return str_out.compareTo(q.Put());

}

public object Copy() // Создание динамической копии объекта

{

return new BigInt(this);

}

public int Add(object q) // Сложение объектов

{

if (Type()!=q.Type()) return 0;

add((BigInt)q);

return 1;

}

///////////////////////////////////////////////////////////////////////////

public boolean getsign()

{

return (pd[sz-1] & 0x80) !=0;

}

public boolean inc()

{

int i;

for (i=0;i<sz;i++)

{

pd[i]++;

if (pd[i]!=0) break;

}

return i==sz;

}

void neg()

{

for (int i=0;i<sz;i++) pd[i] = (byte) ~pd[i];

inc();

}

void denormalize(int n) //0 - после основного числа

{

if(n<=sz) return;

byte[] pdd=pd;

pd=new byte[n];

for(int i=0;i<sz;i++)

pd[i]=pdd[i];

for(int i=sz;i<n;i++)

{

if ((pd[sz-1] & 0x80)==0) pd[i]=0;

else pd[i]=(byte) 0xFF;

}

sz=n;

}

void normalize()

{

for(;sz>1 && ((pd[sz-1]==pd[sz-2] && pd[sz-1]==0) || (pd[sz-1]==pd[sz-2] && pd[sz-1]==-1));sz--);

if(sz>1)

{

if (pd[sz-1]==0 && (pd[sz-2] & 0x80)==0) sz--;

else

if (pd[sz-1]==-1)

if(((pd[sz-2] & 0x80)!=0) && (pd[sz-2]!= -128)) sz--;

}

byte[] ppd=new byte[sz];

for(int i=0;i<sz;i++)

ppd[i]=pd[i];

pd = ppd;

}

//----------------------------------------------------------------------

BigInt(long n)

{

sz=8;

pd=new byte[sz];

for(int i=0;i<sz;i++)

{

pd[i]=(byte)n;

n>>=8;

}

normalize();

}

//---------------------------------------------------------------

BigInt()

{

sz=1;

pd=new byte[sz];

pd[0]=0;

}

BigInt(String str)

{

sz=1;

pd=new byte[sz];

pd[0]=0;

In(str);

}

//------------------------------------------------

public void In(String str)

{

int i;

for (i=0;i<sz;i++) pd[i]=0;

i=0; if (str.charAt(0)=='+' || str.charAt(0)=='-') i=1;

for (; i<str.length();i++)

{

int c=str.charAt(i)-'0';

if (c<0 || c>9) continue;

mul(new BigInt(10));

add(new BigInt(c));

}

if (str.charAt(0)=='-') neg();

normalize();

}

int GetNum()

{

BigInt p=(BigInt) this.Copy();

BigInt a=new BigInt(10);

int i;

for(i=1;p.pd[0]!=0;i++)

p=p.sdiv((BigInt)a.Copy());

return (getsign() || pd[0]==0) ? i : i-1;

}

void lshift()

{

int carry; // Бит переноса

int i,z;

denormalize(sz+1);

for (carry=0, i=0; i<sz; i++)

{

z=(pd[i] & 0x80) >> 7; // Выделить старший бит (перенос)

pd[i] <<= 1; // Сдвинуть влево и установить

pd[i] |=carry; // старый перенос в младший бит

carry = z; // Запомнить новый перенос

}

normalize();

}

void rshift()

{

int i;

int carry; // Бит переноса

int z;

for (carry=0, i=sz-1; i>=0; i--)

{

z = pd[i] & 1; // Выделить младший бит (перенос)

pd[i] >>= 1; // Сдвинуть вправо и установить

pd[i]&=0x7F;

pd[i] |= carry << 7; // старый перенос в старший бит

carry = z; // Запомнить новый перенос

}

}

void mul(BigInt R) //------Умножение целых произвольной разрядности

{

BigInt p=(BigInt) this.Copy();

int i;

for (i=0; i<sz; i++)

pd[i]=0;

for (i=0;i<R.sz*8;i++)

{ // Цикл по количеству битов

if((R.pd[0]&1)==1) // Разряд множителя равен 1

add(p); // Добавить множимое к произведению

p.lshift(); // Множимое - влево

R.rshift(); // Множитель - вправо

}

normalize();

}

public void smul(BigInt R)

{

if(R.getsign())

{

R.neg();

mul(R);

neg();

}

else

{

if(getsign())

{

neg();

mul(R);

neg();

}

else mul(R);

}

}

void div(BigInt R1)

{

BigInt R=(BigInt)R1.Copy();

BigInt x=new BigInt();

int i;

R.denormalize(sz);

x.denormalize(sz);

denormalize(2*sz);

int nn=sz*4;

for (i=0; i<nn-1; i++) R.lshift();

for (i=0; i<nn; i++)

{

R.neg();

add(R);

R.neg();

x.lshift();

if (getsign()) add(R);

else x.pd[0]|=1;

R.rshift();

}

pd=x.pd;

sz=x.sz;

normalize();

}

void __sdiv(BigInt R)

{

if(R.getsign() && getsign())

{

R.neg();

neg();

div(R);

return;

}

if(R.getsign())

{

R.neg();

div(R);

return;

}

else

{

if(getsign())

{

neg();

div(R);

}

else div(R);

}

}

public BigInt sdiv(BigInt R)

{

BigInt q=(BigInt)this.Copy();

q.__sdiv(R);

return q;

}

public void add(BigInt R)

{

int n=max(sz,R.sz)+1;

denormalize(n);

R.denormalize(n);

int i, w,carry;

for (i=0, carry=0; i<n; i++)

{

w = (pd[i] & 0x0FF)+(R.pd[i] & 0x0FF)+carry;

pd[i] = (byte)w;

carry = ((w & 0x0100) >> 8);

}

normalize();

R.normalize();

}

public void sub(BigInt R)

{

R.neg();

add(R);

R.neg();

}

BigInt(BigInt R)

{

sz=R.sz;

pd=new byte[sz];

for(int i=0;i<sz;i++)

pd[i]=R.pd[i];

}

public int GetSize()

{

return sz;

}

public byte GetPD(int n)

{

return pd[n];

}

BigInt mod(BigInt R)

{

BigInt th=(BigInt) this.Copy();

BigInt x=new BigInt();

int i;

R.denormalize(sz);

x.denormalize(sz);

for (i=0; i<sz*8-1; i++){ R.lshift();}

int nn=sz*8;

for (i=0; i<nn; i++)

{

R.neg();

th.add(R);

R.neg();

x.lshift();

if (th.getsign())

th.add(R);

else{

x.pd[0]|=1;

}

R.rshift();

}

x.normalize();

th.normalize();

return th;

}

public String Out()

{

int n=GetNum();

int i;

byte[] c=new byte[n];

String str=new String();

BigInt p=(BigInt) this.Copy();

BigInt t;

BigInt a=new BigInt(10);

int k=0;

if(getsign())

{

k++;

p.neg();

}

for(i=0;p.pd[0]!=0;i++)

{

t=p.mod((BigInt)a.Copy());

c[i]=(byte) (t.pd[0]+'0');

p=p.sdiv((BigInt)a.Copy());

}

if(k==1) c[i++]='-';

if(pd[0]==0){ c[0]='0'; i++;}

byte[] str_out=new byte[n];

int j,g;

for(j=i-1,g=0;j>=0;j--,g++)

str_out[g]=c[j];

str=new String(str_out);

return str;

}

}