Cod sursa(job #1814131)

Utilizator geniucosOncescu Costin geniucos Data 23 noiembrie 2016 18:02:12
Problema Eval Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.75 kb
#include<bits/stdc++.h>
#define base 10
#define base_length 1

using namespace std;

int pos, step, mod, nr, pr[200], rr[200], x[200], rest[30][200];
char sir[100009];

int pow (int a, int b, int mod)
{
    int p = 1;
    for (int i=0; (1<<i) <= b; i++)
    {
        if (b & (1 << i)) p = (1LL * p * a) % mod;
        a = (1LL * a * a) % mod;
    }
    return p;
}

bool prime (int val)
{
    for (int i=2; i<=70; i++)
        if (pow (i, val - 1, val) != 1) return 0;
    return 1;
}

void GetPrimes ()
{
    double need = 1000 + log10 (2);
    for (int i=1e9 + 1000; i>=1; i--)
        if (prime (i))
        {
            pr[++nr] = i, need -= log10 (i), printf ("%d\n", i);
            if (need < 0) break;
        }
}

void ReadVariables ()
{
    int n;
    char sir[1004];
    scanf ("%d\n", &n);
    for (int i=0; i<n; i++)
    {
        int beg = 1, L;
        gets (sir + 1), L = strlen (sir + 1);
        if (sir[1] == '-') beg = 2;
        for (int j=1; j<=nr; j++)
        {
            for (int k=beg; k<=L; k++)
                rest[i][j] = ((long long) rest[i][j] * 10 + sir[k] - '0') % pr[j];
            if (sir[1] == '-') rest[i][j] = (pr[j] - rest[i][j]) % pr[j];
        }
    }
}

vector < int > get_vect (int val)
{
    vector < int > v;
    while (val)
        v.push_back (val % base), val /= base;
    return v;
}

vector < int > operator * (vector < int > a, int b)
{
    long long t = 0;
    for (auto it = a.begin (); it != a.end (); it ++)
    {
        long long aux = 1LL * (*it) * b + t;
        (*it) = aux % base, t = aux / base;
    }
    while (t)
        a.push_back (t % base), t /= base;
    while (!a.empty () && (*a.rbegin ()) == 0) a.erase (a.begin () + a.size () - 1);
    return a;
}

vector < int > operator + (vector < int > a, vector < int > b)
{
    while (a.size () < b.size ()) a.push_back (0);
    while (b.size () < a.size ()) b.push_back (0);
    vector < int > c;
    int t = 0;
    for (auto it1 = a.begin (), it2 = b.begin (); it1 != a.end (); it1 ++, it2 ++)
        c.push_back (((*it1) + (*it2) + t) % base),
        t = ((*it1) + (*it2) + t) / base;
    if (t) c.push_back (t);
    return c;
}

vector < int > operator - (vector < int > a, vector < int > b)
{
    while (b.size () < a.size ()) b.push_back (0);
    vector < int > c;
    int t = 0;
    for (auto it1 = a.begin (), it2 = b.begin (); it1 != a.end (); it1 ++, it2 ++)
        if ((*it1) - (*it2) - t >= 0) c.push_back ((*it1) - (*it2) - t), t = 0;
        else c.push_back ((*it1) - (*it2) - t + base), t = 1;
    while (!c.empty () && (*c.rbegin ()) == 0) c.erase (c.begin () + c.size () - 1);
    return c;
}

void Print (vector < int > v)
{
    if (v.empty ())
    {
        printf ("0\n");
        return ;
    }
    auto it = v.rbegin ();
    printf ("%d", *it);
    for (it ++; it != v.rend (); it ++)
        printf ("%0*d", base_length, *it);
    printf ("\n");
}

void ChineseRemainderTheorem ()
{
    for (int i=1; i<=nr; i++)
    {
        int prod = 1;
        for (int j=1; j<i; j++)
        {
            rr[i] = ((long long) rr[i] - 1LL * x[j] * prod) % pr[i];
            if (rr[i] < 0) rr[i] += pr[i];
            prod = (1LL * prod * pr[j]) % pr[i];
        }
        x[i] = (1LL * rr[i] * pow (prod, pr[i] - 2, pr[i])) % pr[i];
    }
    vector < int > prod = get_vect (1), ans = get_vect (0);
    for (int i=1; i<=nr; i++)
        ans = ans + prod * x[i],
        prod = prod * pr[i];
    if (ans.size () > 250)
        printf ("-"), ans = prod - ans;
    Print (ans);
}

int eval0 ();
int eval1 ();
int eval2 ();
int main ()
{
freopen ("eval.in", "r", stdin);
freopen ("eval.out", "w", stdout);

GetPrimes ();
ReadVariables ();
gets (sir + 1);
for (step = 1; step <= nr; step ++)
    pos = 1, mod = pr[step], rr[step] = eval0 ();
ChineseRemainderTheorem ();
return 0;
}

int eval0 ()
{
    int ans = eval1 ();
    while (sir[pos] == '+' || sir[pos] == '-')
    {
        if (sir[pos] == '+')
        {
            pos ++, ans += eval1 ();
            if (ans >= mod) ans -= mod;
        }
        else
        {
            pos ++, ans -= eval1 ();
            if (ans < 0) ans += mod;
        }
    }
    return ans;
}

int eval1 ()
{
    int ans = eval2 ();
    while (sir[pos] == '*')
        pos ++, ans = (1LL * ans * eval2 ()) % mod;
    return ans;
}

int eval2 ()
{
    if (sir[pos] == '(' || sir[pos] == '[')
    {
        char c = sir[pos ++];
        int ans = eval0 (); pos ++;
        if (c == '[') ans = (1LL * ans * ans) % mod;
        return ans;
    }
    char c = sir[pos]; pos ++;
    if (c == '-') return (mod - eval0 ()) % mod;
    if (c == '+') return eval0 ();
    return rest[c - 'a'][step];
}