题解：AT_abc483_f [ABC483F] Sum of Mod of Linear

UnionRE · 2026-11-10 13:22:22 · 题解

对于比较大的模数，我们考虑离线。

枚举 x。既然模数比较大，那么产生 \bmod b 的次数也比较少。

我们预处理 \mathcal D_i=\{x|x=kb_i-a_i,k\in\mathbb N^*,kb\ge a_i\}。这些点就是产生取模的点。因此经过这些点就把当前答案 -b_i。

对于比较小的模数，按照 b 分组为 G_b，我们设 sum_{u,v} 表示 b_i=u,x\bmod b=v 的答案。cnt_{u,v} 表示 G_u 内 a\bmod u=v 的个数。

满足 sum_{u,v}=\displaystyle\sum_{a\in G_u}(v+a)\bmod u=\sum_{r=0}^{u-1}cnt_{u,r}(v+r)\bmod u。然后枚举 u，查询 sum_{u,x\bmod u}。

我们考虑复杂度分治。

我们设阈值为 B，设 a_i,b_i\le W，那么复杂度：

难以完美平衡。因此我们尝试尽可能让 B 大，因为 W\approx 2.5N。

我这里 B=900，擦限卡过。

对 b_i\le B 的去重，就能快一些。

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
#define fir(i, l, r) for(int i = l; i <= r; i++)
#define fpr(i, r, l) for(int i = r; i >= l; i--)
const int maxn = 5e5 + 10;
int a[maxn], b[maxn], ub[maxn];
const int B = 900;
long long val[B + 10][B + 10], ans[maxn], sum[B + 10][B + 10], cnt[B + 10], pf[maxn];
array <int, 2> x[maxn]; 
basic_string <int> vec[maxn], v[maxn];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen(".in", "r", stdin);
    // freopen(".out", "w", stdout);
    int n, q, sa = 0, mx = 0;
    cin >> n;
    fir(i, 1, n) cin >> a[i] >> b[i], a[i] %= b[i], sa += a[i], vec[b[i]] += a[i];
    cin >> q;
    fir(i, 1, q) cin >> x[i][0], x[i][1] = i, mx = max(mx, x[i][0]);
    fir(i, 1, B){
        fir(j, 0, i - 1) cnt[j] = 0;
        for(auto j : vec[i]) cnt[j]++;
        fir(j, 0, i - 1){
            fir(r, 0, i - 1) sum[i][j] += 1ll * cnt[r] * ((j + r) % i);
        }
    }
    sort(x + 1, x + q + 1);
    int cnt = 0, tot = 0;
    fir(i, 1, n){
        if(b[i] <= B){
            ub[++tot] = b[i];
            continue ;
        }
        cnt++;
        for(int p = b[i] - a[i]; p < maxn; p += b[i]) v[p].push_back(b[i]);
    }
    sort(ub + 1, ub + tot + 1);
    tot = unique(ub + 1, ub + tot + 1) - ub - 1;
    int lax = 0;
    long long f = 0;
    fir(i, 1, n) if(b[i] > B) f += a[i];
    pf[0] = f;
    fir(i, 1, mx){
        f += cnt;
        for(auto j : v[i]) f -= j;
        pf[i] = f;
    }
    fir(i, 1, q){
        auto [xx, id] = x[i];
        ans[id] = pf[xx];
        fir(j, 1, tot) ans[id] += sum[ub[j]][xx % ub[j]];
    }
    fir(i, 1, q) cout << ans[i] << endl;
    return 0;
}