Eous的小站
日记

日记

Thu Jan 09 2025
6 分钟
life 日记
1157 字

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

上午#

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

T1#

赛时想法：∅\empty

T2#

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

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

T3#

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

T4#

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

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

中午#

颓废了一中午。

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

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

下午#

改题。

T1#

直到现在都云里雾里的。

T2#

一道 dp，码量奇大无比。

以下为 自己骂自己：

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

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

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

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

你 ******。

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

T3#

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

T4#

sourcesolution

记录一下解题思路：

根据不知道叫啥反正是个定理，每个数都可以分解成 ∏piei\prod p_{i}^{e_{i}}。而这个数的因数数量就是 ∏(ei+1)\prod (e_{i} + 1)。于是我们就只用关心 ee 了。对于每一个数 ii 都有一个可重集 vi={e1,e2,e3,⋯ ,en}v_{i} = \{e_{1},e_{2},e_{3},\cdots,e_{n}\}。其中有 ei≥ei+1e_{i} \ge e_{i + 1}。可以证明一共只有 289289 个不同的 SS（可惜我不会）。设 valival_{i} 为 ii 的最小质因数，mpvi,jmp_{v_{i},j} 表示把集合 viv_{i} 变到有 jj 个因数的最小步数。初始状态 mpv1,1=0mp_{v_{1},1} = 0。考虑转移：

mpv1,i=mpv1,ivali+vali−1mp_{v_{1},i} = mp_{v_{1},\frac{i}{val_{i}}} + val_{i} - 1

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

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

那如果没有 pp 怎么办，也很简单。我们只用修改 eie_{i} 最小的质因数，枚举 k∈[2,+∞]k \in [2,+ \infty]，然后用 vk×jv_{k \times j} 转移 SjS_{j}。

贴一下代码：

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