CF1792E题解

yimuhua · 2023-01-28 16:53:02 · 题解

首先对 m_1,m_2 分解质因数，然后组合起来暴力搜出 m 的所有因数，因数数量大约是 O(m^{\frac{1}{3}})，对于 m\le 10^8 最多为 105000 个。

将 m 的因数按从小到大存在 d_1,d_2,\dots,d_l 中，对于每一个 d_i，我们要求一个最小的 x 满足 x 是 d_i 的因数且 \dfrac{d_i}{x}\le n。

于是先二分出一个 d_j 满足 d_j\ge \left\lceil\dfrac{d_i}{n}\right\rceil 然后向后遍历直到 d_j 为 d_i 的一个因数或 d_j>\min(n,d_i)

代码：

#include <bits/stdc++.h>
using namespace std;
vector<long long> a;
map<long long, long long> mp;
long long t, n, m, m2, cnt, ans;
vector<pair<long long, long long> > v;
void dfs(long long x, long long s) {
    if(x == v.size()) {
        a.push_back(s);
        return;
    }
    auto j = v[x];
    for(long long i = 0; i <= j.second; i++) {
        dfs(x + 1, s);
        if(i != j.second)
            s *= j.first;
    }
    return;
}
void init() {
    v.clear();
    for(long long i = 2; i < 100001; i++)
        if(!(m % i))
            while(!(m % i))
                mp[i]++, m /= i;
    if(m > 1)
        mp[m]++;
    for(long long i = 2; i < 100001; i++)
        if(!(m2 % i))
        while(!(m2 % i))
            mp[i]++, m2 /= i;
    if(m2 > 1)
        mp[m2]++;
    for(auto i : mp)
        v.push_back(i);
    dfs(0, 1);
    return;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    while(t--) {
        cin >> n >> m >> m2, mp.clear(), a.clear(), init(), sort(a.begin(), a.end()), ans = cnt = 0;
        for(long long i : a) {
            auto it = lower_bound(a.begin(), a.end(), (i - 1) / n + 1);
            if(*it <= n) {
                while(it != a.end() && i % *it) {
                    it++;
                    if(it != a.end() && *it > n)
                        break;
                }
                if(it != a.end() && *it <= n)
                    cnt++, ans ^= *it;
            }
        }
        cout << cnt << ' ' << ans << '\n';
    }
    return 0;
}