2018 计蒜之道 初赛 第五场
本文最后更新于 2116 天前,其中的信息可能已经有所发展或是发生改变。

内容纲要

由题可知最大情况为(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;
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇