Pagini recente » Cod sursa (job #1252277) | Cod sursa (job #847804) | Cod sursa (job #1552339) | Cod sursa (job #2855730) | Cod sursa (job #1814133)
#include<bits/stdc++.h>
#define base 10000
#define base_length 4
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 + 10000; i>=1; i--)
if (prime (i))
{
pr[++nr] = i, need -= log10 (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];
}