作业题解

c_legg · 2026-04-25 18:51:51 · 题解

考虑根号分治，设值域为 V。

首先我们有一个阈值 B，对所有 0\le j\lt i\le B，用 \text{bit}_{i, j} 表示 S 中是否有一个数 x 使得 x\equiv j\pmod i。

然后我们也要用一个 set 来表示 S（记作 \text{st}）。

在执行操作一时，我们维护上述的 \text{st} 和 \text{bit}。

执行操作二时，我们可以对 y 进行分类：若 y\le B，从小到大遍历 \text{bit}_y 找到第一个存在的数，时间复杂度为 O(B)；若 y\gt B，在 set 中二分找到第一个大于等于 0,y,2y,\cdots 的数，并对 y 取模后求最小值，时间复杂度为 O(\frac{V\log V}{B})。

然后当 \frac{V\log V}{B}+B 最小时最优（B\approx 1281.84881184），求出 B，问题就解决了。

注意：然而 set 的二分查找是有常数的，所以 B\neq 1282 时可能更优（实际上 B\approx 640 时最优），不过 B=1282 时也能过。

#include <bits/stdc++.h>

// using pii=std::pair<int, int>;

const int sq(650);

int q;

std::bitset<sq+5> bit[sq+5];

std::set<int> st;

void solve() {
    std::cin>>q;
    while(q--) {
        char op;
        int x;
        std::cin>>op>>x;
        if(op=='A') {
            st.insert(x);
            for(int i(1); i<=sq; i++) bit[i][x%i]=1;
        } else {
            if(x<=sq) {
                for(int i(0); i<x; i++) {
                    if(bit[x][i]) { std::cout<<i<<"\n"; break; }
                }
            } else {
                int ans(300000+5);
                for(int i(0); i<=300000; i+=x) {
                    auto j(st.lower_bound(i));
                    if(j==st.end()) continue;
                    ans=std::min(ans, (*j)%x);
                }
                std::cout<<ans<<"\n";
            }
        }
    }
}

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    solve();
    return 0;
}