Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define task "COMNUM"
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <cstring>
- #include <iomanip>
- #include <vector>
- #include <cmath>
- using namespace std;
- using ll = long long;
- using ld = long double;
- constexpr int N = 1e5 + 5;
- using Integer = ll;
- string l, r;
- void Read()
- {
- cin >> l >> r;
- reverse(l.begin(), l.end());
- while (l.size() < r.size())
- l.push_back('0');
- reverse(l.begin(), l.end());
- }
- /*Subtask 1*/
- ll toLL(const string &s)
- {
- ll ans(0);
- for (auto i : s)
- ans = ans * 10 + i - '0';
- return ans;
- }
- ll Get(ll v)
- {
- ll ans(1);
- while (v)
- {
- ans *= v % 10;
- v /= 10;
- }
- return ans;
- }
- void Sub_1() // Duyệt từ L đến R
- {
- ll L = toLL(l),
- R = toLL(r), ans(0);
- while (L <= R)
- ans = max(ans, Get(L++));
- cout << ans;
- }
- /*End subtask 1*/
- /*Subtask 2*/
- ll dp[20][2][2];
- // Hàm lấy giá trị của số y, chú ý nếu như chữ số ở vị trí đầu tiên (x == 0) thì coi như số đó chưa bắt đầu, nên trả về 1
- inline int Get(int x, int y)
- {
- if (y == 0)
- return x == 0 ? 1 : 0;
- return y;
- }
- ll f(int i, bool gtl, bool ltr) // dp digit
- {
- ll &ans = dp[i][gtl][ltr];
- if (ans != -1)
- return ans;
- if (i == (int)r.size())
- return (ans = 1);
- ans = 0;
- for (int j = '0'; j <= '9'; ++j)
- if ((gtl || j >= l[i]) && (ltr || j <= r[i]))
- ans = max(ans, f(i + 1, gtl || j > l[i], ltr || j < r[i]) * Get(i, j - '0'));
- return ans;
- }
- void Sub_2()
- {
- memset(dp, -1, sizeof dp);
- cout << f(0, 0, 0);
- }
- /*End subtask 2*/
- /*Subtask 3*/
- const int M = 1e2 + 10; // Số lượng chữ số ước tính của đáp án
- const ll BASE = 1e7; // Hệ cơ số
- const int gd = log10(BASE);
- const int maxn = M / gd + 1; // Số phần tử của mảng
- struct Bignum
- {
- int n;
- ll a[maxn];
- Bignum(ll x = 0)
- {
- memset(a, 0, sizeof a);
- n = 0;
- do
- {
- a[n++] = x % BASE;
- x /= BASE;
- } while (x);
- }
- void fix()
- {
- ++n;
- for (int i = 0; i < n - 1; ++i)
- {
- a[i + 1] += a[i] / BASE;
- a[i] %= BASE;
- if (a[i] < 0)
- {
- a[i] += BASE;
- --a[i + 1];
- }
- }
- while (n > 1 && a[n - 1] == 0)
- --n;
- }
- // Vì chỉ nhân với số nguyên nên có thể nhân trong O(n)
- Bignum &operator*=(const ll &x)
- {
- for (int i = 0; i < n; ++i)
- a[i] *= x;
- fix();
- return *this;
- }
- Bignum &operator*=(const Bignum &x)
- {
- vector<ll> c(n + x.n);
- for (int i = 0; i < n; ++i)
- for (int j = 0; j < x.n; ++j)
- c[i + j] += a[i] * x.a[j];
- n += x.n - 1;
- for (int i = 0; i < n; ++i)
- a[i] = c[i];
- fix();
- return *this;
- }
- Bignum operator*(const Bignum &s)
- {
- Bignum c;
- copy(a, a + n, c.a);
- c.n = n;
- c *= s;
- return c;
- }
- bool operator<(const Bignum &s) const
- {
- if (n < s.n)
- return true;
- if (n > s.n)
- return false;
- for (int i = n - 1; i > -1; --i)
- if (a[i] > s.a[i])
- return false;
- else if (a[i] < s.a[i])
- return true;
- return false;
- }
- friend ostream &operator<<(ostream &out, const Bignum &x)
- {
- int i = x.n;
- while (i > 0 && x.a[i] == 0)
- --i;
- out << x.a[i];
- for (--i; ~i; --i)
- out << setw(gd) << setfill('0') << x.a[i];
- return out;
- }
- };
- Bignum Pow9[M];
- void Sub_3()
- {
- int pos(0);
- for (; pos < (int)r.size() && l[pos] == r[pos]; ++pos);
- Bignum pre(1), ans(0);
- Pow9[0] = Bignum(1);
- for (int i = 1; i <= (int)r.size(); ++i)
- {
- Pow9[i] = Pow9[i - 1];
- Pow9[i] *= 9ll;
- if (i <= pos)
- pre *= (ll)(r[i - 1] - '0');
- }
- for (int i = pos; i <= (int)r.size(); ++i)
- {
- Bignum temp = pre * Pow9[max(0, (int)r.size() - i - 1)];
- if (i < (int)r.size())
- {
- temp *= (ll)Get(i, max(0, r[i] - '0' - 1));
- pre *= (ll)(r[i] - '0');
- }
- if (ans < temp)
- ans = temp;
- }
- cout << ans;
- }
- int32_t main()
- {
- ios::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- freopen(task ".INP", "r", stdin);
- freopen(task ".OUT", "w", stdout);
- Read();
- if ((int)r.size() <= 6)
- Sub_1();
- else if ((int)r.size() <= 18)
- Sub_2();
- else if ((int)r.size() <= 100)
- Sub_3();
- }
Add Comment
Please, Sign In to add comment