Who can help me. I use big int class in c++.

Edited by author 15.08.2010 19:36

maybe your long arithmetics works too slow.
what base are you using when performing adding/multiplying? what about algo?

Edited by author 15.08.2010 20:20

Edited by author 16.08.2010 12:46

// 1012.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <deque>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
using namespace std;
const int SZ = 1000;

class verylong
{
private:
deque<char>vlstr;
int vlen;
verylong multdigit(const int) const;
verylong mult10(const verylong) const;
public:
verylong() : vlen(0)
{ vlstr[0]='\0'; }
verylong(const char s[SZ])
{ strcpy(vlstr, s); vlen=strlen(s); }
verylong(const unsigned long n)
{
sprintf(vlstr, "%lu", n);
_strrev(vlstr);
vlen=strlen(vlstr);
}
void putvl() const;
void getvl();
verylong operator + (const verylong);
verylong operator * (const verylong);
verylong operator - (const verylong);
};
//--------------------------------------------------------------

void verylong::putvl() const
{
char temp[SZ];
strcpy(temp,vlstr);
cout << _strrev(temp);
}
//--------------------------------------------------------------
void verylong::getvl()
{
cin >> vlstr;
vlen = strlen(vlstr);
_strrev(vlstr);
}
//--------------------------------------------------------------
verylong verylong::operator + (const verylong v)
{
char temp[SZ];
int j;

int maxlen = (vlen > v.vlen) ? vlen : v.vlen;
int carry = 0;
for(j = 0; j<maxlen; j++)
{
int d1 = (j > vlen-1)   ? 0 : vlstr[j]-'0';
int d2 = (j > v.vlen-1) ? 0 : v.vlstr[j]-'0';
int digitsum = d1 + d2 + carry;
if( digitsum >= 10 )
{ digitsum -= 10; carry=1; }
else
carry = 0;
temp[j] = digitsum+'0';
}
if(carry==1)
temp[j++] = '1';
temp[j] = '\0';
return verylong(temp);
}
//--------------------------------------------------------------
verylong verylong::operator - (const verylong v)
{
char temp[SZ];
    int j, p=0, r=0;

    int maxlen = (vlen > v.vlen) ? vlen : v.vlen;
    p = maxlen - 1;
    int carry = 0;

    for(j=0; j<maxlen; j++)
    {
        int d1 = (j > vlen-1) ? 0 : vlstr[j] - '0';
        int d2 = (j > v.vlen - 1) ? 0 : v.vlstr[j] - '0';
        int digitdif = d1 - d2 - carry;
        if(digitdif < 0)
        { digitdif += 10;  carry = 1; }
        else carry = 0;
        temp[j] = digitdif + '0';
    }
    temp[j] = '\0';

    return verylong(temp);
}
//--------------------------------------------------------------
verylong verylong::operator * (const verylong v)
{
verylong pprod;
verylong tempsum;
for(int j=0; j<v.vlen; j++)
{
int digit = v.vlstr[j]-'0';
pprod = multdigit(digit);
for(int k=0; k<j; k++)
pprod = mult10(pprod);
tempsum = tempsum + pprod;
}
return tempsum;
}
//--------------------------------------------------------------
verylong verylong::mult10(const verylong v) const
{
char temp[SZ];
for(int j=v.vlen-1; j>=0; j--)
temp[j+1] = v.vlstr[j];
temp[0] = '0';
temp[v.vlen+1] = '\0';
return verylong(temp);
}
//--------------------------------------------------------------
verylong verylong::multdigit(const int d2) const
{
char temp[SZ];
int j, carry = 0;
for(j = 0; j<vlen; j++)
{
int d1 = vlstr[j]-'0';
int digitprod = d1 * d2;
digitprod += carry;
if( digitprod >= 10 )
{
carry = digitprod/10;
digitprod -= carry*10;
}
else
carry = 0;
temp[j] = digitprod+'0';
}
if(carry != 0)
temp[j++] = carry+'0';
temp[j] = '\0';
return verylong(temp);
}


int main()
{
    verylong a[180], s[180];
    unsigned long n, i, k;
    scanf("%d", &n);
    scanf("%d", &k);

    a[0] = (n-n);
    s[0] = (k-1);


    for(i=1; i<n; i++)
    {
        s[i] = (verylong)k * s[i-1];
        s[i] = s[i] - a[i-1];
        a[i] = s[i-1] - a[i-1];
    }

    s[n-1].putvl();
    return 0;
}

waiting....

Hi, I think the major problem is operator *. You seem to use vlen of verylong objects store the intermediate value. That's not a good idea, as 10-based long algorithm already has the risk of TLE, let alone that staff. Try not to use multy10 but to store intermediate value in a char array instead. I can send you my code (in C). btw, VC2010 compiler says it doesn't allow using deque as an argument of strxxx. How did you pass compilation with this code?

You don't necessarily use *. + is enough. And quicker.
 I've tested. It works in this way very fast. Remember to enlarge array.

Edited by author 19.08.2010 13:36

Edited by author 19.08.2010 13:46

My int main algo is right or not?


I wrote it in VC 2010.
You must wipe out #include "stdafx.h"
and main function must be int main()

Edited by author 19.08.2010 14:10

my mail:


johnterryr@mail.ru

I think algo all right. But it won't compile if using deque. After changing it into char[5000] it works, producing the same answer for 1800,10 as mine. However, for input 10,2 the output is 089, I don't know why. I'll send you my program later this evening.

yes i wanted change answers like that into 89 , But i sent it and AC.And i didn't take care of it after AC,

Sent. See email for detail.

thanks

Here is my simple program
//////////
#include<iostream>
using namespace std;
int main()
{
  int a[2000]={0},b[2000]={0},c[2000]={0};
  int g,n,k,i,j,m=1,t=2000;
  cin>>n>>k;
  a[t-1]=1; b[t-1]=k-1;
  for(i=2;i<=n;i++)
  {
    g=0;
    for(j=t-1;j>=t-m;j--)
    {
     c[j]=a[j]+b[j];
     c[j]=c[j]*(k-1)+g;
     if (c[j]>9) {g=c[j]/10; c[j]=c[j]%10; }else g=0;
     a[j]=b[j]; b[j]=c[j];
    }
    if (g!=0)
    {
        m++;
        b[t-m]=g; c[t-m]=g;
    }
  }
  for(j=t-m;j<t;j++) cout<<c[j];
}

it's amazing ... bravo!

Do not make recursive calls, instead use a register of 3 values, f(N-1), f(N-2) and the one you are calculating: f(N). Then calculate all values from i=2 to N and use register. This reduces memory requirements :), makes the code for this problem faster.