Cod sursa(job #1778146)

Utilizator Sanduleac_VladSanduleac Vllad Alexandru Sanduleac_Vlad Data 13 octombrie 2016 15:45:45
Problema Next Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.83 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
const int MAX_DIGITS = 1000000;
const int BASE = 10;
const int MAX_INT = (1LL << 31) - 1;

class HugeN {
    private: int x[MAX_DIGITS + 5];
public:
    HugeN() {
        x[0] = 1;
        for(int i = 1; i <= MAX_DIGITS; i++)
            x[i] = 0;
    }
    HugeN(int nr) {
        for(int i = 0; i <= MAX_DIGITS; i++)
            x[i] = 0;
        do {
            x[++x[0]] = nr % 10;
            nr /= BASE;
        } while(nr);
    }
    HugeN(HugeN &other) {
        for(int i = 0; i <= MAX_DIGITS; i++)
            x[i] = 0;
        memcpy(x, other.x, sizeof(other.x));
    }
    HugeN(char *s) {
        x[0] = strlen(s);
        for(int i = 1; i <= x[0]; i++)
            x[i] = s[x[0] - i] - '0';
    }

    void print() {
        int i;
        for(i = x[0]; i >= 1; i--)
            printf("%d", x[i]);
        printf("\n");
    }
    int cmp(const HugeN &other);
    HugeN operator+(const HugeN &other);
    HugeN operator-(const HugeN &other);
    HugeN operator-(int k);
    HugeN operator*(int k);
    HugeN operator*(const HugeN &other);
    HugeN operator/(int k);
    HugeN operator/(const HugeN &other);
    int operator%(int k);
    long long operator%(long long k);
    HugeN operator%(const HugeN &other);
    HugeN operator^(int k);
    HugeN operator+=(const HugeN &other);
    HugeN operator+=(long long k);
    HugeN operator-=(const HugeN &other);
    HugeN operator*=(int k);
    HugeN operator*=(const HugeN &other);
    HugeN operator/=(int k);
    bool operator>(const HugeN &other);
    bool operator>=(const HugeN &other);
    bool operator<(const HugeN &other);
    bool operator<=(const HugeN &other);
    bool operator==(const HugeN &other);
    bool operator!=(const HugeN &other);
};

int HugeN::cmp(const HugeN &other) {
    int i;
    if(x[0] > other.x[0])
        return 1;
    if(x[0] < other.x[0])
        return -1;
    if(x[i] > other.x[i])
        return 1;
    else if(x[i] < other.x[i])
        return -1;
    return 0;
}

HugeN HugeN::operator+(const HugeN &other) {
    HugeN temp;
    temp.x[0] = x[0] > other.x[0] ? x[0] : other.x[0];
    int tr = 0, aux, i;
    for(i = 1; i <= temp.x[0]; i++) {
        aux = x[i] + other.x[i] + tr;
        temp.x[i] = aux % BASE;
        tr = aux / BASE;
    }
    if(tr)
        temp.x[++temp.x[0]] = tr;
    return temp;
}

HugeN HugeN::operator+=(const HugeN &other) {
    x[0] = x[0] > other.x[0] ? x[0] : other.x[0];
    int tr = 0, aux, i;
    for(i = 1; i <= x[0]; i++) {
        aux = x[i] + other.x[i] + tr;
        x[i] = aux % BASE;
        tr = aux / BASE;
    }
    if(tr)
        x[++x[0]] = tr;
    return *this;
}

HugeN HugeN::operator+=(long long k) {
    long long tr = 0, aux, i;
    for(i = 1; i <= x[0]; i++) {
        aux = x[i] + k + tr;
        x[i] = aux % BASE;
        tr = aux / BASE;
        k /= 10;
    }
    while(tr) {
        x[++x[0]] = tr % BASE;
        tr = tr / BASE;
    }
    return *this;
}

bool HugeN::operator>(const HugeN &other) {
    if((*this).cmp(other) == 1)
        return 1;
    return 0;
}

HugeN HugeN::operator*(int k) {
    HugeN temp;
    temp.x[0] = (*this).x[0];
    int i, j;
    unsigned long long carry = 0;
    for(i = 1; i <= (*this).x[0]; i++) {
        carry += (*this).x[i] * k;
        temp.x[i] = carry % BASE;
        carry /= BASE;
    }
    while(carry) {
        temp.x[0]++;
        temp.x[temp.x[0]] = carry % BASE;
        carry /= BASE;
    }
    return temp;
}

HugeN HugeN::operator*=(int k) {
    int i, j;
    long long carry = 0;
    for(i = 1; i <= (*this).x[0]; i++) {
        carry += (*this).x[i] * k;
        x[i] = carry % BASE;
        carry /= BASE;
    }
    while(carry) {
        x[0]++;
        x[x[0]] = carry % BASE;
        carry /= BASE;
    }
    return *this;
}

HugeN HugeN::operator*(const HugeN &other) {
    HugeN temp;
    temp.x[0] = (*this).x[0] + other.x[0] - 1;
    int i, j;
    for(i = 1; i <= (*this).x[0]; i++)
        for(j = 1; j <= other.x[0]; j++) {
            temp.x[i + j - 1] += (*this).x[i] * other.x[j];
            int k = i + j - 1, carry = 0;
            while(temp.x[k] >= BASE) {
                carry = temp.x[k] / BASE;
                temp.x[k] = temp.x[k] % BASE;
                k++;
                temp.x[k] += carry;
                if(temp.x[k] && k >= temp.x[0])
                    temp.x[0] = k;
            }
        }
    return temp;
}

long long HugeN::operator%(long long k) {
    long long aux = 0;
    int i;
    for(i = x[0]; i >= 1; i--) {
        aux = (aux * 10 + x[i]) % k;
    }
    return aux;
}

char *s;
long long D;

int main() {
    int i, j;
    freopen("next.in", "r", stdin);
    freopen("next.out", "w", stdout);
    s = new char[MAX_DIGITS + 10];
    gets(s);
    HugeN N(s);
    delete s;
    scanf("%lld\n", &D);
    D = D - N % D;
    N += D;
    N.print();
    return 0;
}