Pagini recente » Cod sursa (job #613879) | Cod sursa (job #67939)
Cod sursa(job #67939)
using namespace std;
#define MAX_N 1005
#define MAX_D 3005
#define BAZA 10
#define max(a,b) ((a)>(b)?(a):(b))
#include <stdio.h>
#include <string.h>
#include <fstream>
typedef struct
{
int n;
int x[MAX_D];
} bignum;
FILE *fin=fopen("sarpe.in","r"),
*fout=fopen("sarpe.out","w");
bignum n;
bignum sl,p;
void read (void)
{
int i=0;
char c='0';
fscanf(fin,"%c",&c);
while (c>=48 && c<=57) {
n.x[++i]=c-48;
c='x';
fscanf(fin,"%c",&c);
}
n.n=i;
int aux;
for (i=1; i<=n.n/2; i++)
{ aux=n.x[n.n-i+1]; n.x[n.n-i+1]=n.x[i]; n.x[i]=aux; }
}
void multiply (bignum &a, bignum b, bignum c)
{
int t=0,i,j; memset(a.x,0,sizeof(a.x)); a.n=0;
for (i=1; i<=b.n; i++)
for (j=1; j<=c.n; j++)
a.x[i+j-1]+=b.x[i]*c.x[j];
for (i=1; i<=MAX_D; i++) {
a.x[i]=(t+=a.x[i])%BAZA; t/=BAZA; }
for (i=MAX_D; i>=1; i--)
if (a.x[i]!=0) { a.n=i; break; }
if (a.n==0) a.n=1;
}
void multint(bignum &a, int b)
{
int i,t=0;
for (i=1; i<=a.n; i++)
{ a.x[i]=(t+=a.x[i]*b)%BAZA; t/=BAZA; }
if (t>0) a.x[++a.n]=t;
}
void add(bignum &a, bignum b)
{
int i,t=0;
a.n=max(a.n,b.n);
for (i=1; i<=a.n; i++)
{ a.x[i]=(t+=a.x[i]+b.x[i])%BAZA; t/=BAZA; }
if (t>0) a.x[++a.n]=t;
}
void sub(bignum &a,bignum b)
{
int i, t = 0;
for (i = 1; i <= a.n; i++)
a.x[i] += (t = (a.x[i] -= b.x[i] + t) < 0) * BAZA;
for (; a.n > 1 && !a.x[a.n]; a.n--);
}
void solve (void)
{
bignum aux;
int i=1;
i<<=1;
memset(aux.x, 0, sizeof(aux.x));
memcpy(sl.x,n.x,sizeof(n.x)); sl.n=n.n;
multint(sl,4);
p.n=1; p.x[1]=2; aux.n=1; aux.x[1]=1;
sub(n,aux);
multiply(p,p,n);
sub(n,aux);
multiply(p,p,n);
add(sl,p);
return ;
}
void print (void)
{
int i;
fprintf(fout,"%d",sl.x[sl.n]);
for (i=sl.n-1; i>=1; i--)
fprintf(fout,"%d",sl.x[i]);
fprintf(fout,"\n");
}
int main()
{
read();
solve();
print();
fclose(fin);
fclose(fout);
return 0;
}