Pagini recente » Cod sursa (job #256858) | Cod sursa (job #2821392) | Cod sursa (job #2225265) | Cod sursa (job #652874) | Cod sursa (job #1524105)
#include <fstream>
#include <algorithm>
#include <cstring>
#define D 40000
using namespace std;
ifstream f("next.in");
ofstream g("next.out");
typedef int Huge[4000];
Huge a,b,d,r;
int n,i;
char c=0;
void Shl(Huge H, int Count)
/* H <- H*10ACount */
{
/* Shifteaza vectorul cu Count pozitii */
memmove(&H[Count+1],&H[1],sizeof(int)*H[0]);
/* Umple primele Count pozitii cu 0 */
memset(&H[1],0,sizeof(int)*Count);
/* Incrementeaza numarul de cifre */
H[0]+=Count;
}
int Sgn(Huge H1, Huge H2) {
// Elimina zero-urile semnificative, daca exista.
while (H1[0] && !H1[H1[0]]) H1[0]--;
while (H2[0] && !H2[H2[0]]) H2[0]--;
if (H1[0] < H2[0]) {
return -1;
} else if (H1[0] > H2[0]) {
return +1;
}
for (int i = H1[0]; i > 0; --i) {
if (H1[i] < H2[i]) {
return -1;
} else if (H1[i] > H2[i]) {
return +1;
}
}
return 0;
}
void Subtract(Huge a,Huge b)
{ int i, T=0;
for (i=b[0]+1;i<=a[0];) b[i++]=0;
for (i=1;i<=a[0];i++)
a[i]+= (T=(a[i]-=b[i]+T)<0) ? 10 : 0;
while (!a[a[0]]) a[0]--;
}
void Add(Huge a, Huge b)
/* a <- a+b */
{ int i,T=0;
if (b[0]>a[0])
{ for (i=a[0]+1;i<=b[0];) a[i++]=0;
a[0]=b[0];
}
else for (i=b[0]+1;i<=a[0];) b[i++]=0;
for (i=1;i<=a[0];i++)
{ a[i]+=b[i]+T;
T=a[i]/10;
a[i]%=10;
}
if (T) a[++a[0]]=T;
}
void DivideHuge(Huge A, Huge B, Huge C, Huge R)
/* A/B = C rest R */
{ int i;
R[0]=0;C[0]=A[0];
for (i=A[0];i;i--)
{ Shl(R,1);R[1]=A[i];
C[i]=0;
while (Sgn(B,R)!=1)
{ C[i]++;
Subtract(R,B);
}
}
while (!C[C[0]] && C[0]>1) C[0]--;
}
int main()
{ f.get(c);
while(c!='\n')
{ a[++a[0]]=c-'0';
f.get(c);
}
reverse(a+1,a+a[0]+1);
f.get(c);
while(c!='\n')
{ b[++b[0]]=c-'0';
f.get(c);
}
reverse(b+1,b+b[0]+1);
DivideHuge(a,b,d,r);
if(r) {Subtract(b,r);Add(a,b);}
for(int i=a[0];i>=1;i--) g<<a[i];
return 0;
}