Cod sursa(job #2472892)

Utilizator vladth11Vlad Haivas vladth11 Data 13 octombrie 2019 09:47:05
Problema A+B Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 21.27 kb
#include <bits/stdc++.h>

using namespace std;
///Euleeer
int phi[1000001];
int euler()
{
    int n,i,j;
    cin >> n;
    for(i = 2;i <= n;i++){
        phi[i] = i;
    }
    for(i = 2;i <= n;i++){
        if(phi[i] == i){
            for(j = i;j <= n;j+=i){
                phi[j] -= (phi[j] / i);
            }
        }
    }
    long long sum = 0;
    for(i = 0;i <= n;i++){
        sum += phi[i];
    }
    cout << sum * 2 + 1;
    return 0;
}
///Combinari cu pascal
int binomialCoeff(int n, int k)
{
    int C[k+1];
    memset(C, 0, sizeof(C));

    C[0] = 1;  // nC0 is 1

    for (int i = 1; i <= n; i++)
    {
        // Compute next row of pascal triangle using
        // the previous row
        for (int j = min(i, k); j > 0; j--)
            C[j] = C[j] + C[j-1];
    }
    return C[k];
}
///Catalan
///Al treilea catalan
unsigned long int binomialCoeff(unsigned int n, unsigned int k)
{
    unsigned long int res = 1;

    // Since C(n, k) = C(n, n-k)
    if (k > n - k)
        k = n - k;

    // Calculate value of [n*(n-1)*---*(n-k+1)] / [k*(k-1)*---*1]
    for (int i = 0; i < k; ++i)
    {
        res *= (n - i);
        res /= (i + 1);
    }

    return res;
}

// A Binomial coefficient based function to find nth catalan
// number in O(n) time
unsigned long int catalann(unsigned int n)
{
    // Calculate value of 2nCn
    unsigned long int c = binomialCoeff(2*n, n);

    // return 2nCn/(n+1)
    return c/(n+1);
}
///Al doilea catalan
unsigned long int catalanDP(unsigned int n)
{
    // Table to store results of subproblems
    unsigned long int catalan[n+1];

    // Initialize first two values in table
    catalan[0] = catalan[1] = 1;

    // Fill entries in catalan[] using recursive formula
    for (int i=2; i<=n; i++)
    {
        catalan[i] = 0;
        for (int j=0; j<i; j++)
            catalan[i] += catalan[j] * catalan[i-j-1];
    }

    // Return last entry
    return catalan[n];
}
///Primul catalan
unsigned long int catalan(unsigned int n)
{
    // Base case
    if (n <= 1) return 1;

    // catalan(n) is sum of catalan(i)*catalan(n-i-1)
    unsigned long int res = 0;
    for (int i=0; i<n; i++)
        res += catalan(i)*catalan(n-i-1);

    return res;
}

/*RMQ 2D
int n;
int sparse[505][505][18];
int v[505][505];
int logs[505];
void precalculate()
{
    logs[1] = 0;
    for(int i = 2; i <= n; i++)
    {
        logs[i] = logs[i/2] + 1;
    }
}
void build()
{
    for(int k = 0; k <= logs[n]; k++)
    {
        int lungime = (1 << k);
        for(int i = 1; i + lungime <= n + 1; i++)
        {
            for(int j = 1; j + lungime <= n + 1; j++)
            {
                if(lungime != 1)
                {
                    sparse[i][j][k] = max(sparse[i][j][k-1],max(sparse[i + lungime / 2][j][k-1],max(sparse[i][j + lungime / 2][k-1],sparse[i + lungime / 2][j + lungime / 2][k-1])));
                }else{
                    sparse[i][j][k] = v[i][j];
                }
            }
        }
    }
}
int getmin(int x,int y,int k){
    int p = logs[k];
    int lung = (1 << p);
    int i = x + k;
    int j = y + k;
    return max(sparse[x][y][p],max(sparse[i - lung][y][p],max(sparse[x][j - lung][p],sparse[i - lung][j - lung][p])));
}*/
///Al k-lea nr fibonacci
const int MOD = 666013;
struct matrice
{
    long long m[2][2];
    void clearr(){
        for(int i = 0;i < 2;i++){
            for(int j = 0;j < 2;j++){
                m[i][j] = 0;
            }
        }
    }
    matrice operator * (matrice const a)
    const{
        matrice rez;
        rez.clearr();
        for(int i = 0; i < 2; i++)
        {
            for(int j = 0; j < 2; j++)
            {
                rez.m[i][j] = 0;
                for(int k = 0; k < 2; k++)
                {
                    rez.m[i][j] += m[i][k] * a.m[k][j];
                    rez.m[i][j] %= MOD;
                }
            }
        }
        return rez;
    }
};
matrice exp(matrice n,int p)
{
    matrice rest;
    int i,j;
    for(i = 0; i < 2; i++)
        for(j = 0; j < 2; j++)
        {
            rest.m[i][j] = n.m[i][j];
        }
    while(p)
    {
        if(p % 2)
        {
            rest = rest * n;
        }
        n = n * n;
        p >>= 1;
    }
    return rest;
}
int funcct()
{
    int n,i,j;
    cin >> n;
    matrice init;
    init.m[0][0] = init.m[1][0] = init.m[0][1] = 1;
    init.m[1][1] = 0;
    cout << exp(init,n  -2).m[0][0] ;
    return 0;
}
///Disjoint
int numar[100001],principal[10001];
int radacina(int x){
    if(principal[x] == 0)
        return x;
    principal[x] = radacina(principal[x]);
    return principal[x];
}
void reuniune(int x,int y){
    int a = radacina(x),b = radacina(y);
    if(numar[a] > numar[b])
    {
        numar[a] += numar[b];
        principal[b] = a;
    }else{
        numar[b] += numar[a];
        principal[a] = b;
    }
}
bool verific(int x,int y){
    if(radacina(x) == radacina(y))
        return true;
    return false;
}

///Invers Modular
int euler(int n){
     long long d = 2, p, prod = n;
    while ( d * d <= n ) {
        p = 0;
        while ( n % d == 0 ) {
            n /= d;
            p ++;
        }
        if ( p )
            prod = prod / d * ( d - 1 );
        d ++;
    }
    if ( n > 1 )
        prod = prod / n * ( n - 1 );
    return prod;
}
int putere(int a,int n,int m){
    int prod = 1;
    do{
        if(n%2 != 0){
            prod = (long long)prod * a % m;
        }
        a = 1LL * a * a % m;
        n /= 2;
    }while(n != 0);
    return prod;
}
///RMQ 1D
int logs[100001];
int n,m;
int sparse[18][100001];
int cv[100001];
void precalculate(){
    logs[1] = 0;
    for(int i = 2;i <= n;i++){
        logs[i] = logs[i/2] + 1;
    }
}
void build(){
    for(int i = 0;i <= logs[n];i++){
        int lungime = (1 << i);
        for(int j = 1;j + lungime <= n + 1;j++){
            if(lungime != 1)
                sparse[i][j] = min(sparse[i - 1][j],sparse[i-1][j + lungime / 2]);
            else
                sparse[0][j] = cv[j];
        }

    }
    sparse[0][n] = cv[n];
}
int getmin(int l,int r){
    int p = logs[r - l + 1];
    return min(sparse[p][l],sparse[p][r - (1 << p) + 1]);
}
///lgput
long long exponentiere(long long n,long long p)
{
    long long rest = 1;
    while(p)
    {
        if(p % 2)
        {
          rest *= n;
            //rest %= MOD;
        }
        n *= n;
        //n %= MOD;
        p >>= 1;
    }

    return rest;
}
///Numere marii
const int base = 1000000000;
const int base_digits = 9;
struct bigint
{
    vector<int> a;
    int sign;

    bigint() :
        sign(1)
    {
    }

    bigint(long long v)
    {
        *this = v;
    }

    bigint(const string &s)
    {
        read(s);
    }

    void operator=(const bigint &v)
    {
        sign = v.sign;
        a = v.a;
    }

    void operator=(long long v)
    {
        sign = 1;
        if (v < 0)
            sign = -1, v = -v;
        for (; v > 0; v = v / base)
            a.push_back(v % base);
    }

    bigint operator+(const bigint &v) const             //Addition Operation
    {
        if (sign == v.sign)
        {
            bigint res = v;
            for (int i = 0, carry = 0; i < (int) max(a.size(), v.a.size()) || carry; ++i)
            {
                if (i == (int) res.a.size())
                    res.a.push_back(0);
                res.a[i] += carry + (i < (int) a.size() ? a[i] : 0);
                carry = res.a[i] >= base;
                if (carry)
                    res.a[i] -= base;
            }
            return res;
        }
        return *this - (-v);
    }

    bigint operator-(const bigint &v) const             //Subtraction Function
    {
        if (sign == v.sign)
        {
            if (abs() >= v.abs())
            {
                bigint res = *this;
                for (int i = 0, carry = 0; i < (int) v.a.size() || carry; ++i)
                {
                    res.a[i] -= carry + (i < (int) v.a.size() ? v.a[i] : 0);
                    carry = res.a[i] < 0;
                    if (carry)
                        res.a[i] += base;
                }
                res.trim();
                return res;
            }
            return -(v - *this);
        }
        return *this + (-v);
    }

    void operator*=(int v)                      //Multiplication Function
    {
        if (v < 0)
            sign = -sign, v = -v;
        for (int i = 0, carry = 0; i < (int) a.size() || carry; ++i)
        {
            if (i == (int) a.size())
                a.push_back(0);
            long long cur = a[i] * (long long) v + carry;
            carry = (int) (cur / base);
            a[i] = (int) (cur % base);
            //asm("divl %%ecx" : "=a"(carry), "=d"(a[i]) : "A"(cur), "c"(base));
        }
        trim();
    }

    bigint operator*(int v) const
    {
        bigint res = *this;
        res *= v;
        return res;
    }

    friend pair<bigint, bigint> divmod(const bigint &a1, const bigint &b1)
    {
        int norm = base / (b1.a.back() + 1);
        bigint a = a1.abs() * norm;
        bigint b = b1.abs() * norm;
        bigint q, r;
        q.a.resize(a.a.size());
        for (int i = a.a.size() - 1; i >= 0; i--)
        {
            r *= base;
            r += a.a[i];
            int s1 = r.a.size() <= b.a.size() ? 0 : r.a[b.a.size()];
            int s2 = r.a.size() <= b.a.size() - 1 ? 0 : r.a[b.a.size() - 1];
            int d = ((long long) base * s1 + s2) / b.a.back();
            r -= b * d;
            while (r < 0)
                r += b, --d;
            q.a[i] = d;
        }

        q.sign = a1.sign * b1.sign;
        r.sign = a1.sign;
        q.trim();
        r.trim();
        return make_pair(q, r / norm);
    }

    bigint operator/(const bigint &v) const                 //Division Function
    {
        return divmod(*this, v).first;
    }

    bigint operator%(const bigint &v) const                 //Modulus Operation
    {
        return divmod(*this, v).second;
    }

    void operator/=(int v)                                  //Shorthand Operation
    {
        if (v < 0)
            sign = -sign, v = -v;
        for (int i = (int) a.size() - 1, rem = 0; i >= 0; --i)
        {
            long long cur = a[i] + rem * (long long) base;
            a[i] = (int) (cur / v);
            rem = (int) (cur % v);
        }
        trim();
    }

    bigint operator/(int v) const
    {
        bigint res = *this;
        res /= v;
        return res;
    }

    int operator%(int v) const
    {
        if (v < 0)
            v = -v;
        int m = 0;
        for (int i = a.size() - 1; i >= 0; --i)
            m = (a[i] + m * (long long) base) % v;
        return m * sign;
    }

    void operator+=(const bigint &v)
    {
        *this = *this + v;
    }
    void operator-=(const bigint &v)
    {
        *this = *this - v;
    }
    void operator*=(const bigint &v)
    {
        *this = *this * v;
    }
    void operator/=(const bigint &v)
    {
        *this = *this / v;
    }

    bool operator<(const bigint &v) const
    {
        if (sign != v.sign)
            return sign < v.sign;
        if (a.size() != v.a.size())
            return a.size() * sign < v.a.size() * v.sign;
        for (int i = a.size() - 1; i >= 0; i--)
            if (a[i] != v.a[i])
                return a[i] * sign < v.a[i] * sign;
        return false;
    }

    bool operator>(const bigint &v) const
    {
        return v < *this;
    }
    bool operator<=(const bigint &v) const
    {
        return !(v < *this);
    }
    bool operator>=(const bigint &v) const
    {
        return !(*this < v);
    }
    bool operator==(const bigint &v) const
    {
        return !(*this < v) && !(v < *this);
    }
    bool operator!=(const bigint &v) const
    {
        return *this < v || v < *this;
    }

    void trim()
    {
        while (!a.empty() && !a.back())
            a.pop_back();
        if (a.empty())
            sign = 1;
    }

    bool isZero() const
    {
        return a.empty() || (a.size() == 1 && !a[0]);
    }

    bigint operator-() const
    {
        bigint res = *this;
        res.sign = -sign;
        return res;
    }

    bigint abs() const
    {
        bigint res = *this;
        res.sign *= res.sign;
        return res;
    }

    long long longValue() const
    {
        long long res = 0;
        for (int i = a.size() - 1; i >= 0; i--)
            res = res * base + a[i];
        return res * sign;
    }

    friend bigint gcd(const bigint &a, const bigint &b)             //GCD Function(Euler Algorithm)
    {
        return b.isZero() ? a : gcd(b, a % b);
    }
    friend bigint lcm(const bigint &a, const bigint &b)             //Simple LCM Operation
    {
        return a / gcd(a, b) * b;
    }

    void read(const string &s)                                  //Reading a Big Integer
    {
        sign = 1;
        a.clear();
        int pos = 0;
        while (pos < (int) s.size() && (s[pos] == '-' || s[pos] == '+'))
        {
            if (s[pos] == '-')
                sign = -sign;
            ++pos;
        }
        for (int i = s.size() - 1; i >= pos; i -= base_digits)
        {
            int x = 0;
            for (int j = max(pos, i - base_digits + 1); j <= i; j++)
                x = x * 10 + s[j] - '0';
            a.push_back(x);
        }
        trim();
    }

    friend istream& operator>>(istream &stream, bigint &v)
    {
        string s;
        stream >> s;
        v.read(s);
        return stream;
    }

    friend ostream& operator<<(ostream &stream, const bigint &v)
    {
        if (v.sign == -1)
            stream << '-';
        stream << (v.a.empty() ? 0 : v.a.back());
        for (int i = (int) v.a.size() - 2; i >= 0; --i)
            stream << setw(base_digits) << setfill('0') << v.a[i];
        return stream;
    }

    static vector<int> convert_base(const vector<int> &a, int old_digits, int new_digits)
    {
        vector<long long> p(max(old_digits, new_digits) + 1);
        p[0] = 1;
        for (int i = 1; i < (int) p.size(); i++)
            p[i] = p[i - 1] * 10;
        vector<int> res;
        long long cur = 0;
        int cur_digits = 0;
        for (int i = 0; i < (int) a.size(); i++)
        {
            cur += a[i] * p[cur_digits];
            cur_digits += old_digits;
            while (cur_digits >= new_digits)
            {
                res.push_back(int(cur % p[new_digits]));
                cur /= p[new_digits];
                cur_digits -= new_digits;
            }
        }
        res.push_back((int) cur);
        while (!res.empty() && !res.back())
            res.pop_back();
        return res;
    }

    typedef vector<long long> vll;

    static vll karatsubaMultiply(const vll &a, const vll &b)        //Multiplication using Karatsuba Algorithm
    {
        int n = a.size();
        vll res(n + n);
        if (n <= 32)
        {
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    res[i + j] += a[i] * b[j];
            return res;
        }

        int k = n >> 1;
        vll a1(a.begin(), a.begin() + k);
        vll a2(a.begin() + k, a.end());
        vll b1(b.begin(), b.begin() + k);
        vll b2(b.begin() + k, b.end());

        vll a1b1 = karatsubaMultiply(a1, b1);
        vll a2b2 = karatsubaMultiply(a2, b2);

        for (int i = 0; i < k; i++)
            a2[i] += a1[i];
        for (int i = 0; i < k; i++)
            b2[i] += b1[i];

        vll r = karatsubaMultiply(a2, b2);
        for (int i = 0; i < (int) a1b1.size(); i++)
            r[i] -= a1b1[i];
        for (int i = 0; i < (int) a2b2.size(); i++)
            r[i] -= a2b2[i];

        for (int i = 0; i < (int) r.size(); i++)
            res[i + k] += r[i];
        for (int i = 0; i < (int) a1b1.size(); i++)
            res[i] += a1b1[i];
        for (int i = 0; i < (int) a2b2.size(); i++)
            res[i + n] += a2b2[i];
        return res;
    }

    bigint operator*(const bigint &v) const
    {
        vector<int> a6 = convert_base(this->a, base_digits, 6);
        vector<int> b6 = convert_base(v.a, base_digits, 6);
        vll a(a6.begin(), a6.end());
        vll b(b6.begin(), b6.end());
        while (a.size() < b.size())
            a.push_back(0);
        while (b.size() < a.size())
            b.push_back(0);
        while (a.size() & (a.size() - 1))
            a.push_back(0), b.push_back(0);
        vll c = karatsubaMultiply(a, b);
        bigint res;
        res.sign = sign * v.sign;
        for (int i = 0, carry = 0; i < (int) c.size(); i++)
        {
            long long cur = c[i] + carry;
            res.a.push_back((int) (cur % 1000000));
            carry = (int) (cur / 1000000);
        }
        res.a = convert_base(res.a, 6, base_digits);
        res.trim();
        return res;
    }
};
///Parsare
class InParser
{
private:
    FILE *fin;
    char *buff;
    int sp;

    char read_ch()
    {
        ++sp;
        if (sp == 4096)
        {
            sp = 0;
            fread(buff, 1, 4096, fin);
        }
        return buff[sp];
    }

public:
    InParser(const char* nume)
    {
        fin = fopen(nume, "r");
        buff = new char[4096]();
        sp = 4095;
    }

    InParser& operator >> (int &n)
    {
        char c;
        while (!isdigit(c = read_ch()) && c != '-');
        int sgn = 1;
        if (c == '-')
        {
            n = 0;
            sgn = -1;
        }
        else
        {
            n = c - '0';
        }
        while (isdigit(c = read_ch()))
        {
            n = 10 * n + c - '0';
        }
        n *= sgn;
        return *this;
    }

    InParser& operator >> (long long &n)
    {
        char c;
        n = 0;
        while (!isdigit(c = read_ch()) && c != '-');
        long long sgn = 1;
        if (c == '-')
        {
            n = 0;
            sgn = -1;
        }
        else
        {
            n = c - '0';
        }
        while (isdigit(c = read_ch()))
        {
            n = 10 * n + c - '0';
        }
        n *= sgn;
        return *this;
    }
};

struct ura
{
    long double x,y;
} v[100001];
long double sol = 0;
///aria unui poligon
void aria()
{
    int n,i;
    //cin >> n;
    for(i = 1; i <= n; i++)
    {
        //cin >> v[i].x >> v[i].y;
    }
    v[n + 1].x = v[1].x;
    v[n + 1].y = v[1].y;
    for(i = 1; i <= n; i++)
    {
        sol += (v[i].x * v[i + 1].y - v[i+1].x * v[i].y);
    }
    sol /= 2;
    //cout <<fixed<<setprecision(10)<< sol;
}
///Ciclu in graf gangster
struct Edge
{
    long long u;
    long long v;
    long long weight;
};
class Graph
{
    long long V ;
    list < pair <long long, long long > >*adj;

    vector < Edge > edge;

public :
    Graph( long long V )
    {
        this->V = V ;
        adj = new list < pair <long long, long long > >[V];
    }

    void addEdge ( long long u, long long v, long long w );
    void removeEdge( long long u, long long v, long long w );
    long long  ShortestPath (long long u, long long v );
    void RemoveEdge( long long u, long long v );
    long long FindMinimumCycle ();

};

void Graph :: addEdge ( long long u, long long v, long long w )
{
    adj[u].push_back( make_pair( v, w ));
    adj[v].push_back( make_pair( u, w ));

    Edge e { u, v, w };
    edge.push_back (  e );
}
void Graph :: removeEdge ( long long u, long long v, long long w )
{
    adj[u].remove(make_pair( v, w ));
    adj[v].remove(make_pair(u, w ));
}
long long Graph :: ShortestPath ( long long u, long long v )
{

    set< pair<long long, long long> > setds;


    vector<long long> dist(V, 2e9);
    setds.insert(make_pair(0, u));
    dist[u] = 0;

    while (!setds.empty())
    {

        pair<long long, long long> tmp = *(setds.begin());
        setds.erase(setds.begin());
        long long u = tmp.second;

        list< pair<long long, long long> >::iterator i;
        for (i = adj[u].begin(); i != adj[u].end(); ++i)
        {
            long long v = (*i).first;
            long long weight = (*i).second;

            if (dist[v] > dist[u] + weight)
            {
                if (dist[v] != 2e9)
                    setds.erase(setds.find(make_pair(dist[v], v)));

                dist[v] = dist[u] + weight;
                setds.insert(make_pair(dist[v], v));
            }
        }
    }

    return dist[v] ;
}
long long Graph :: FindMinimumCycle ( )
{
    long long min_cycle = 2e9;
    long long E = edge.size();
    for ( long long i = 0 ; i < E  ; i++ )
    {
        Edge e = edge[i];


        removeEdge( e.u, e.v, e.weight ) ;

        long long vistance = ShortestPath( e.u, e.v );

        min_cycle = min( min_cycle, vistance + e.weight );

        addEdge( e.u, e.v, e.weight );
    }

    return min_cycle ;
}
///Adunare
int main()
{
    ifstream cin("adunare.in");
    ofstream cout("adunare.out");
    bigint a,b;
    cin >> a >> b;
    cout << a + b;
    return 0;
}