题解：P13016 [GESP202506 六级] 最大因数

A7F3jK9pR0xf_ · 2025-06-30 17:41:32 · 题解

题目传送门

思路

设 k 质因数分解后的 k=\Pi_{i=1}^m\alpha_i(\alpha从小到大排，可重复)，那么根据整数的唯一分解定理，显然它的第 \beta 级祖先为 \Pi_{i=\beta+1}^m\alpha_i。那就好做了，先给 x 和 y 质因数分解，存到 mp[0] 和 mp[1] 里面，计算交集 s，想算 LCA 那么只需要计算交集里最大的下标 id 使得 mp[0][s[id]] 和 mp[1][s[id]] 不相等即可。答案就是 \sum_{i=1}^{id-1}mp_{0,s_i}+mp_{1,s_i}+|mp_{0,s_{id}}-mp_{1,s_{id}}|，时间复杂度 O(q\sqrt n\log\sqrt n)，\log 是 map 贡献的。

Code

#include <bits/stdc++.h>
using namespace std;
#define il inline
#define fst first
#define sed second
#define ins insert
#define cl clear
map<int, int> mp[2];
set<int> s;
il void qwq(int x, int id)
{
    for(int i = 2;i <= x / i;++i)
    {
        while(x % i == 0)
        {
            mp[id][i]++;
            s.ins(i);
            x /= i;
        }
    }
    if(x > 1)
    {
        mp[id][x]++;
        s.ins(x);
    }
}
int main()
{
    int q;cin >> q;
    while(q--)
    {
        s.cl(), mp[0].cl(), mp[1].cl();
        int x, y;cin >> x >> y;
        if(x == y)
        {
            cout << "0\n";
            continue;
        }
        qwq(x, 0);qwq(y, 1);
        int cnt = 0, id = 0;
        for(auto i : s)
            if(mp[0][i] != mp[1][i]) id = i;
        for(auto i : s)
        {
            if(i > id) break;
            if(i == id) cnt += abs(mp[0][i] - mp[1][i]);
            else cnt += mp[0][i] + mp[1][i];
        }
        cout << cnt << "\n";
    } 
    return 0;
}