2018 计蒜之道 初赛 第五场

由题可知最大情况为(n + 1) * 3 * 3 - n，然而我们无法得知最小情况时三个数之间的关系。

故考虑DP打表，算出某个数两个数相乘时最小的值，由该值递推第三个数。

打表算法O(nlogn)，查询O(1)

A题代码

#pragma GCC optimize("O3")
#include <iostream>
#include <vector>
#include <array>
#include <queue>
#include <algorithm>
#include <deque>
#include <cmath>
#include <cstring>

using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int maxn = 1e6 + 6;
int T, n;
array<int, maxn> dp, dp2;

int main() {
    ios::sync_with_stdio(false);
    ([&]() -> void {
        dp.fill(1e9);
        dp2.fill(1e9);
        for (int i = 1; i <= 1e6; ++i) {
            for (int j = 1; i * j <= 1e6; ++j) {
                dp[i * j] = min(dp[i * j], (i + 2) * (j + 2));
            }
        }
        for (int i = 1; i <= 1e6; ++i) {
            for (int j = 1; i * j <= 1e6; ++j) {
                dp2[i * j] = min(dp2[i * j], dp[i] * (j + 1));
            }
        }
    })();
    cin >> T;
    while (T--) {
        cin >> n;
        int ansmax = (n + 1) * 3 * 3 - n;
        int ansmin = dp2[n] - n;
        cout << ansmin << " " << ansmax << endl;
    }
}

B

根据题意枚举n范围内的f(x),用哈希表保存，打表结束后对表进行枚举，算出符合条件的个数即可

B/C题代码:

#pragma GCC optimize("O3")

#include <iostream>
#include <algorithm>
#include <array>
#include <limits>
#include <cmath>
#include <map>
#include <iomanip>
#include <unordered_map>
#include <regex>
#include <queue>
#include <functional>

using namespace std;
using ll = long long;
using db = double;
using pll = pair<ll, ll>;
const ll mod = 998244353;

ll f(ll x) {
    ll ans = 1;
    while (x) {
        ans *= (x % 10);
        x /= 10;
    }
    return ans;
}

unordered_map<ll, ll> mp;

int main() {
    ios::sync_with_stdio(false);
    ll n, k;
    cin >> n >> k;
    ll cnt = 0;
    for (ll i = 1; i <= n; ++i) {
        ll fi = f(i);
        if (fi)
            ++mp[fi];
    }
    for (auto i:mp) {
        for (auto j:mp) {
            ll g = __gcd(i.first, j.first);
            if (g > 0 && g <= k) {
                cnt = (cnt + i.second * j.second) % mod;
            }
        }
    }
    cout << cnt << endl;
}