Codeforces Round 900（Div.3） E~F

E. Iva & Pav

因为按位与的结果不会随着越多数字的增加而增加，因此我们可以利用这个性质二分出右端点，只需要一个可以查询区间的数据结构即可。

或者是按位考虑第 \(i\) 个数字的第 \(k\) 位，后缀最近的 \(0\) 的位置，按位考虑也可以。但是这题使用二分会比较更好地考虑。

template <typename _Ty, typename _Oper>
class SparseTable {
private:
    std::vector<std::vector<_Ty>> _f;
    _Oper _oper;
    std::size_t _n;

public:
    using value_type = _Ty;
    using operator_type = _Oper;

private:
    explicit SparseTable(std::size_t n, _Ty value, _Oper oper)
        : _f(std::bit_width(n), std::vector<_Ty>(n, value)),
          _oper(std::move(oper)), _n(n) {}

public:
    template <std::input_iterator __Iter, typename __Oper>
        requires requires(typename std::iterator_traits<__Iter>::value_type x,
                          __Oper oper) {
            {
                oper(x, x)
            }
            -> std::same_as<typename std::iterator_traits<__Iter>::value_type>;
        }
    explicit SparseTable(__Iter first, __Iter last, __Oper oper)
        : SparseTable(std::distance(first, last),
                      (typename __Iter::value_type){}, std::move(oper)) {
        std::copy(first, last, _f[0].begin());

        for (std::size_t i = 1; i < _f.size(); i++) {
            for (std::size_t j = 0; j + (1 << i) - 1 < _n; j++) {
                _f[i][j] = _oper(_f[i - 1][j], _f[i - 1][j + (1 << (i - 1))]);
            }
        }
    }

    auto Ask(std::size_t l, std::size_t r) const -> _Ty {
        auto s = std::bit_width(r - l) - 1;
        return _oper(_f[s][l], _f[s][r - (1 << s)]);
    }

    auto Size() const noexcept -> std::size_t {
        return _n;
    }
};

template <typename __Iter, typename __Oper>
explicit SparseTable(__Iter, __Iter, __Oper)
    -> SparseTable<typename std::iterator_traits<__Iter>::value_type, __Oper>;

void Main() {
    int n;
    std::cin >> n;
    
    std::vector<int> a(n);
    for (auto &x : a) {
        std::cin >> x;
    }

    SparseTable st(a.begin(), a.end(), std::bit_and{});
    auto GetLast = [&](int first, int k) -> int {
        int l = first + 1, r = n, last = -1;
        while (l <= r) {
            auto mid = std::midpoint(l, r);
            if (st.Ask(first, mid) >= k) {
                last = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return last;
    };

    int q;
    std::cin >> q;
    for (int t = 0; t < q; t += 1) {
        int l, k;
        std::cin >> l >> k;
        l -= 1;
        std::cout << GetLast(l, k) << " \n"[t + 1 == q];   
    }
}

F. Vasilije Loves Number Theory

由唯一分解定理，可得 \(n = \prod_{i=1}^{m} p_{i}^{a_i}\) ，其因子个数 \(d(n) = \prod_{i=1}^{m}(a_i + 1)\) 。

因为 \(d(x)\) 是积性函数，所以有 \(d(ab) = d(a)d(b)\) 。

题目要问是否存在一个数 \(a\) ，使得 \(\gcd(a, n) = 1\) 且 \(d(an) = n\) 。对于后者，我们可以将其改写为 \(n = d(a)d(n)\) ，则此时有 \(d(a) = \cfrac{n}{d(n)}\) 。由于因子个数一定是一个正整数，因此，存在一个合法的 \(a\) 的前提条件就自然是 \(d(n) \mid n\) 。

那么我们要怎么确定可以从求得的 \(d(a)\) 知道是否能够构造出一个合法的 \(a\) 呢？很简单，只需要挑几个非常大的素数，能够构成 \(a\) 即可，此时两个数的因子集合没有交集，自然满足 \(\gcd(a, n) = 1\) 了。

最后一个问题： \(n\) 可能过大，怎么办？

我们发现，给定的 \(q\) 很小，小到甚至我们每次做一次 \(O(\sqrt x)\) 的质因数分解，都不会超时，因此，我们可以将 \(n\) 分解，对于之后的 \(x\) 也是分解，并添加进之前分解的结果中。

此时我们要知道 \(d(n) \mid n\) 是否成立，只需要先计算出 \(d(n)\) ，然后看是否 \(d(n)\) 分解后是否是 \(n\) 的子集，即可。

void Main() {
    int n, q;
    std::cin >> n >> q;

    auto Calc = [](auto &mp, auto n, auto d) {
        for (int i = 2; i * i <= n; i += 1) {
            if (n % i == 0) {
                int cnt = 0;
                while (n % i == 0) {
                    n /= i;
                    cnt += 1;
                }
                d /= mp[i] + 1;
                d *= (mp[i] += cnt) + 1;
            }
        }
        if (n > 1) {
            d /= mp[n] + 1;
            d *= (mp[n] += 1) + 1;
        }
        return d;
    };

    std::map<int,int> pre;
    i64 pred = Calc(pre, n, i64(1));

    auto mp = pre;
    auto d = pred;
    
    for (int t = 0; t < q; t += 1) {
        int opt;
        std::cin >> opt;

        if (opt == 1) {
            int x;
            std::cin >> x;
            d = Calc(mp, x, d);

            auto tmp = d;
            for (auto [x, y] : mp) {
                while (y > 0 && tmp % x == 0) {
                    tmp /= x;
                    y --;
                }
            }

            if (tmp == 1) {
                std::cout << "YES\n";
            } else {
                std::cout << "NO\n";
            }
        } else {
            mp = pre;
            d = pred;
        }
    }
    std::cout << '\n';
}