题解：CF1792E Divisors and Table

_pig_ · 2026-08-07 20:59:36 · 题解

先处理出 m_1,m_2 的质因数和次数，合并一下，然后搜索出 m_1m_2 的所有因数。

考虑每个因数 d，如果比 n 小可以直接放在第一排，即 f_d=1。否则，考虑所有的 \frac{d}{p}，p 是之前处理出来的质因数，统计所有的 f_{\frac{d}{p}}\times p，如果在方格内，那就统计，取最小值即可。

#include <bits/stdc++.h>
#define int long long
#define x first
#define y second
using namespace std;
typedef pair <int, int> pii;
int T, n, m1, m2;
vector <pii> v1, v2, v;
vector <int> d;
unordered_map <int, int> f;
void dfs(int pos, int mul)
{
    if (pos == v.size ()) return d.push_back (mul), void ();
    for (int i = 0, j = 1; i <= v[pos].y; i++, j *= v[pos].x)
        dfs (pos + 1, mul * j);
}
signed main()
{
    cin >> T;
    while (T--)
    {
        cin >> n >> m1 >> m2;
        v1.clear (), v2.clear (), v.clear (), d.clear (), f.clear ();
        for (int i = 2; i * i <= m1; i++)
        {
            if (m1 % i) continue;
            int cnt = 0;
            while (m1 % i == 0) m1 /= i, cnt++;
            v1.push_back ({i, cnt});
        }
        if (m1 != 1) v1.push_back ({m1, 1});
        for (int i = 2; i * i <= m2; i++)
        {
            if (m2 % i) continue;
            int cnt = 0;
            while (m2 % i == 0) m2 /= i, cnt++;
            v2.push_back ({i, cnt});
        }
        if (m2 != 1) v2.push_back ({m2, 1});
        // for (pii i : v1) cout << i.x << " " << i.y << "\n";
        // cout << "\n";
        // cout << "\n";
        // for (pii i : v2) cout << i.x << " " << i.y << "\n";
        // cout << "\n";
        int pi = 0, pj = 0; 
        for (;pi < v1.size () && pj < v2.size ();)
        {
            if (v1[pi].x < v2[pj].x) v.push_back (v1[pi++]);
            else if (v1[pi].x > v2[pj].x) v.push_back (v2[pj++]);
            else v.push_back ({v1[pi].x, v1[pi].y + v2[pj].y}), pi++, pj++;
        }
        while (pi < v1.size ()) v.push_back (v1[pi++]);
        while (pj < v2.size ()) v.push_back (v2[pj++]);
        // for (pii i : v) cout << i.x << " " << i.y << "\n";
        // cout << "\n";
        dfs (0, 1);
        sort (d.begin (), d.end ());
        // for (int i : d) cout << i << " ";
        // cout << "\n";
        int ans = 0, cnt = 0;
        for (int i = 0; i < d.size (); i++)
        {
            if (d[i] <= n) f[d[i]] = 1;
            else
            {
                f[d[i]] = 2e9;
                for (int j = 0; j < v.size (); j++)
                {
                    if (d[i] % v[j].x || !f[d[i] / v[j].x]) continue;
                    int x = f[d[i] / v[j].x] * v[j].x;
                    if (x <= n && d[i] / x <= n) f[d[i]] = min ({f[d[i]], x, d[i] / x});
                }
                if (f[d[i]] == 2e9) f[d[i]] = 0;
            }
            if (f[d[i]]) cnt++, ans ^= f[d[i]];
            // cout << d[i] << " " << f[i] << '\n';
        }
        cout << cnt << " " << ans << "\n";
    }
    return 0;
}