日记 - 伊埃斯的博客站

反正你也写不出来题，不如来写日记。

上午

有日记的那天一定有考试。

T1

赛时想法： $\empty$

T2

赛时做法：先考虑熊熊的方案。很简单，就是先把 $a,b$ 按照和排序，然后依次把 $a_{i} + b_{i} > 0$ 的记录进答案。如果有那种 $a_{i} \times b_{i} < 0$ 的，可以把它放在两边，那样也能够有贡献。

再考虑梦梦的方案。梦梦肯定要尽可能的吧和最小的那对 $a_{i},b_{i}$ 塞进熊熊的区间内。但是他先手，他不知道熊熊如何取，为了尽可能的碰到熊熊的区间，他肯定吧他放在数组的中间，以最大化碰到熊熊区间的可能性。

T3

德塔斯抓克车儿啊，写不了一点。

T4

因为死磕 T2 去了，所以没写。但是似乎有点思路？

看到第一句话，你应该想到这是在考试里写的日记，个人感觉今天要爆零。上面说了 T4 有思路，但是也仅限有思路，因为好歹还是一道 T4 是吧，最后 $10$ min 怎么可能写的完呢？

中午

颓废了一中午。

其实也不是颓废啦，就是无所事事而已。

~~感觉有点浪费时间，但是内耗更浪费时间，所以还是算了，别想了~~

下午

改题。

T1

直到现在都云里雾里的。

T2

一道 dp，码量奇大无比。

以下为 自己骂自己：

你 tm 连蓝色的 dp 都 tmd 写的出来，被 tmd 这么一道小的 dp 创翻了？你 tm 有没有点出息？

你说的对，但是我能做到蓝色紫色 dp 仅限于数位 dp 和板一点的斜率优化 dp。偶尔也能做线性 dp。

但是你 tm 不是切过一道蓝色的线性 dp 吗。

蚁钳是蚁钳，现在是现在。

你 ******。

由于太中二了，所以就不写下去了。

T3

没改。究其原因是去找 T4 题解了。

T4

source↗ solution↗

记录一下解题思路：

根据不知道叫啥反正是个定理，每个数都可以分解成 $\prod p_{i}^{e_{i}}$ 。而这个数的因数数量就是 $\prod (e_{i} + 1)$ 。于是我们就只用关心 $e$ 了。对于每一个数 $i$ 都有一个可重集 $v_{i} = \{e_{1},e_{2},e_{3},\cdots,e_{n}\}$ 。其中有 $e_{i} \ge e_{i + 1}$ 。可以证明一共只有 $289$ 个不同的 $S$ （可惜我不会）。设 $val_{i}$ 为 $i$ 的最小质因数， $mp_{v_{i},j}$ 表示把集合 $v_{i}$ 变到有 $j$ 个因数的最小步数。初始状态 $mp_{v_{1},1} = 0$ 。考虑转移：

mp_{v_{1},i} = mp_{v_{1},\frac{i}{val_{i}}} + val_{i} - 1

为什么可以这么转移呢？因为如果我们想增加因数的个数，无非就是两种方案：新增一个质数或者把某一个原有质数的次数 $+1$ 。显然新增质数更快。所以我们就需要 $val_{i} - 1$ 次操作。

现在考虑 $mp_{v_{i},j}$ 的转移。根据刚刚的结论，可以得出如果存在质因数 $p$ 只在 $i$ 中出现且是次数最小的，那么用它转移 $j$ 是最优的，花费为其出现次数。

那如果没有 $p$ 怎么办，也很简单。我们只用修改 $e_{i}$ 最小的质因数，枚举 $k \in [2,+ \infty]$ ，然后用 $v_{k \times j}$ 转移 $S_{j}$ 。

贴一下代码：

1
#include<bits/extc++.h>
2
#define int long long
3
#define vi vector<int>
4
#define inf 0x3f3f3f3f3f3f3f3f
5
using namespace std;
6
const int maxn = 1e6 + 5,n = 1e6;
7
const int maxm = 300,m = 290;
8
int val[maxn];
9
vi pr,v[maxn];
10
map<vi,vi>mp;
11
void prime()
12
{
13
    for (int i = 2; i <= n; i++)
14
    {
15
        if (!val[i])
16
        {
17
            pr.push_back(i);
18
            val[i] = i;
19
        }
20
        for (auto j = pr.begin(); j != pr.end() && *j * i <= n; j++)
21
        {
22
            val[*j * i] = *j;
23
            if (i % *j == 0)
24
                break;
25
        }
26
    }
27
}
28
signed main()
29
{
30
    prime();
31
    for (int i = 2; i <= n; i++)
32
    {
33
        v[i] = v[i / val[i]];
34
        if (val[i] != val[i / val[i]])
35
            v[i].push_back(2);
36
        else
37
            v[i].back()++;
38
    }
39
    for (int i = 1; i <= n; i++)
40
        sort(v[i].begin(),v[i].end(),greater<int>());
41
    mp[v[1]].resize(maxm);
42
    mp[v[1]][1] = 0;
43
    for (int i = 2; i <= m; i++)
44
        mp[v[1]][i] = mp[v[1]][i / val[i]] + val[i] - 1;
45
    for (int i = 2; i <= n; i++)
46
    {
47
        if (mp.count(v[i]))
48
            continue;
49
        vi tmp = v[i];
50
        tmp.pop_back();
51
        mp[v[i]].resize(maxm);
52
        for (int j = 1; j <= m; j++)
53
            mp[v[i]][j] = mp[tmp][j] + v[i].back() - 1;
54
        for (int j = 1; j <= m; j++)
55
            for (int k = 1; k * j <= m; k++)
56
                mp[v[i]][j * k] = min({mp[v[i]][j * k],mp[tmp][j] + abs(v[i].back() - k),mp[v[i]][j] + k - 1});
57
    }
58
    int t,x,y;
59
    scanf("%lld",&t);
60
    while (t--)
61
    {
62
        scanf("%lld%lld",&x,&y);
63
        int ans = inf;
64
        vi tmp1 = mp[v[x]],tmp2 = mp[v[y]];
65
        for (int i = 1; i <= m; i++)
66
            ans = min(ans,tmp1[i] + tmp2[i]);
67
        printf("%lld\n",ans);
68
    }
69
    return 0;
70
}

Thanks for reading!

日记

周四 1月 09 2025

1113 字 · 6 分钟

life 日记