10.21 so
题单介绍
考虑根号分治（不过我是被人提醒才想到的，我不知道为什么会想到根号分治awa。
先对 $k_i$ 根号分治。
当 $k_i \geq A$ 时，至多有 $\dfrac{n}{A}$ 个位置的函数值小于等于 $n$，直接暴力考虑它在这些位置的函数值是否是对应 $a_i$ 的倍数，这样考虑一个函数的时间复杂度是 $O(\dfrac{n}{A})$，而至多有 $O(n)$ 个函数的 $k_i$ 大于等于 $A$，所以这部分总的时间复杂度是 $O(\dfrac{n^2}{A})$。
当 $k_i \lt A$ 时，至多有 $A$ 种本质不同的 $k_i$，那么对这些函数按 $k_i$ 分类，每一类中有许多 $b_j$。
此时再对 $a_i$ 根号分治。
当 $a_i \geq B$ 时，其至多有 $\dfrac{n}{B}$ 个小于等于 $n$ 的倍数，不妨考虑它的这些倍数，是否被某个一次函数经过了，发现对于同类的一次函数，它们均平行，只有满足等于 $b_j = ga_i-ik_i$ 的该类一次函数才会经过 $(i,ga_i)$，其中 $ga_i$ 表示 $a_i$ 的某个倍数。
所以相当于查询每一类 $k_i$ 中的 $b_j = a_i-ik_i$ 的个数，可以用的用 ```unordered_map``` 记一下，$O(1)$ 查询。
至多有 $n$ 个 $a_i \geq B$，对于每个 $a_i$，至多有 $\dfrac{n}{B}$ 个小于等于 $n$ 的倍数，然后对于每个倍数，要考虑 $A$ 种一次函数中经过 $(i,ga_i)$ 的个数，这样这部分总的时间复杂度就是 $O(\dfrac{n^2A}{B})$。
当 $a_i \lt B$ 时，至多有 $B$ 种本质不同的 $a_i$。
对于一个 $a_i$，考虑每类一次函数，当 $b_i \equiv -ik \pmod a_i$ 时该函数对 $a_i$ 有贡献，所以记录每类函数的 $b_i$ 模 $B$ 种不同的 $a_i$ 的余数的出现次数。
这样被预处理的函数总数是 $O(n)$ 的，并统计了它们的 ￥$b_j$ 对 $O(B)$ 种不同的模数取模时的余数出现个数，这部分的时间复杂度是 $O(nB)$。
查询最多考虑 $O(n)$ 个 $a_i$，每次考虑 $O(A)$ 类函数的贡献，这部分的时间复杂度是 $O(nA)$。
所以最后的时间复杂度是 $O(\dfrac{n^2}{A}+\dfrac{n^2A}{B}+nB+nA)$。
考虑对 $\dfrac{n^2A}{B}+nB$ 使用均值不等式，有 $\dfrac{n^2A}{B}+nB \geq 2\sqrt{n^3A} = 2n^{\frac{3}{2}}A^{\frac{1}{2}}$，当且仅当 $B = \sqrt {nA}$ 时等号成立。
此时要调整 $A$ 使 $2n^{\frac{3}{2}}A^{\frac{1}{2}}+nA+n^2A^{-1}$ 中最后各项的 $n^k$ 中 $k$ 的最大值最小，不妨设 $A = n^x$ 次方，则三项为 $n^{\frac{1}{2}x+\frac{3}{2}}+n^{x+1}=n^{-x+2}$，考虑画出三个关于 $x$ 的一次函数图像，求三者较大值的最小值，容易得出 $x = \dfrac{1}{3}$ 时，时间复杂度最好，为 $O(n^{\frac{5}{3}})$，不知道能不能通过 $n=10^5$（）
此时 $A = n^{\frac{1}{3}},B = n^{\frac{2}{3}}$。
# 一次函数计数问题的根号分治思路（通俗版）
先帮你把问题和思路拆解开，用更直白的语言讲清楚，再梳理复杂度逻辑，最后判断可行性。
## 一、先搞懂要解决什么问题
给定两个核心输入：
1. **n个一次函数**：每个函数形式为 $f_j(x) = k_j \cdot x + b_j$（其中 $j \in [1,n]$，$k_j$、$b_j$ 是给定参数）；
2. **长度为n的序列a**：每个位置 $i \in [1,n]$ 对应一个值 $a_i$。
最终要求：对每个 $i$，统计满足以下两个条件的函数 $f_j$ 的个数：
- 条件1：函数在 $x=i$ 处的结果 $f_j(i) \leq n$；
- 条件2：结果 $f_j(i)$ 能被 $a_i$ 整除（即 $a_i \mid f_j(i)$）。
## 二、核心思路：用“根号分治”拆分难题
根号分治的本质是“按参数规模拆分问题，对不同规模用不同高效方法”，这里会拆两次：先按函数的 $k_j$ 大小拆，再按序列的 $a_i$ 大小拆，避免暴力枚举的 $O(n^2)$ 复杂度。
## 三、分情况处理：把复杂问题拆成3个小任务
先定义两个“阈值” $A$ 和 $B$（后续会讲如何选择最优值），然后分3种情况计算每个 $i$ 的答案。
### 情况1：处理 $k_j \geq A$ 的函数（k值大的函数）
$k_j$ 越大，$f_j(i) = k_j \cdot i + b_j$ 越容易超过 $n$（因为 $i$、$b_j$ 均为正整数）。因此：
- 满足“$f_j(i) \leq n$”的 $i$ 很少：最多只有 $\frac{n}{A}$ 个（比如 $k_j \geq A$ 时，$i$ 最大只能是 $\frac{n}{A}$，否则 $k_j \cdot i$ 会直接超过 $n$）；
- 处理方式：暴力枚举每个 $k_j \geq A$ 的函数，再枚举它能覆盖的 $i$，检查“$f_j(i)$ 是否能被 $a_i$ 整除”，直接计数；
- 时间复杂度：最多 $n$ 个函数，每个函数查 $\frac{n}{A}$ 个 $i$，总耗时 $O\left(\frac{n^2}{A}\right)$。
### 情况2：处理 $k_j < A$ 且 $a_i \geq B$ 的情况（k小但a大）
$k_j < A$ 时，函数“增长平缓”（$i$ 增大时 $f_j(i)$ 涨得慢）；但 $a_i \geq B$ 时，$a_i$ 的“小于等于n的倍数”很少（最多 $\frac{n}{B}$ 个，比如 $a_i=B$ 时，倍数是 $B、2B、…、\lfloor \frac{n}{B} \rfloor \cdot B$）。此时换角度计算：
1. 先给 $k_j$ 分类：因 $k_j < A$，最多只有 $A$ 种不同的 $k$（比如 $k=1、2、…、A-1$），把相同 $k$ 的函数归为一类；
2. 用哈希表记录每类的 $b_j$ 次数：比如对 $k=2$ 的类，用 ``unordered_map`` 记录“$b_j=3$ 出现5次”“$b_j=5$ 出现3次”等；
3. 对每个 $a_i \geq B$ 的 $i$：
- 先找 $a_i$ 所有 $\leq n$ 的倍数 $g$（即 $g = t \cdot a_i$，其中 $t$ 是正整数且 $g \leq n$）；
- 对每个倍数 $g$，要找“满足 $f_j(i)=g$”的函数：代入函数式得 $b_j = g - k_j \cdot i$；
- 对每类 $k_j$（共 $A$ 类），查哈希表中“$b_j = g - k_j \cdot i$”的次数，累加就是这类函数的贡献；
- 时间复杂度：$n$ 个 $a_i$，每个查 $\frac{n}{B}$ 个倍数，每个倍数查 $A$ 类 $k$，总耗时 $O\left(\frac{n^2 A}{B}\right)$。
### 情况3：处理 $k_j < A$ 且 $a_i < B$ 的情况（k小且a小）
$a_i < B$ 时，$a_i$ 的种类很少（最多 $B$ 种，比如 $a=1、2、…、B-1$），可以提前“预处理余数”加速：
1. 预处理阶段（提前算好备用）：
- 对每个 $k_j < A$ 的函数（共 $n$ 个），对所有 $a \in [1,B-1]$，计算“$b_j$ 除以 $a$ 的余数”；
- 用数组记录计数：比如“$k=2$ 类、$a=3$、余数=1”的计数器加1，代表该类中 $b_j \equiv 1 \pmod{3}$ 的函数有1个；
2. 查询阶段（计算每个 $i$ 的答案）：
- 对每个 $a_i < B$ 的 $i$，要满足“$f_j(i)$ 能被 $a_i$ 整除”：代入函数式得 $k_j \cdot i + b_j \equiv 0 \pmod{a_i}$，即 $b_j \equiv -k_j \cdot i \pmod{a_i}$；
- 对每类 $k_j$（共 $A$ 类），直接查“$k_j$ 类、$a=a_i$、余数=$(-k_j \cdot i) \mod a_i$”的计数器值，累加就是贡献；
- 时间复杂度：预处理是 $O(nB)$（$n$ 个函数，每个算 $B$ 个余数），查询是 $O(nA)$（$n$ 个 $i$，每个查 $A$ 类 $k$），总耗时 $O(nB + nA)$。
## 四、复杂度优化：如何选A和B最划算？
将3种情况的复杂度相加，总时间复杂度为：
$$O\left(\frac{n^2}{A} + \frac{n^2 A}{B} + nB + nA\right)$$
核心目标是选 $A$ 和 $B$，让总耗时最小，关键是让各项“量级尽可能接近”（根号分治的核心思想）：
1. 先定 $A$：设 $A = n^x$（$x$ 是常数），代入后分析可知，当 $x = \frac{1}{3}$（即 $A$ 是 $n$ 的立方根）时，各项的“$n$ 的指数”最小；
2. 再定 $B$：根据 $A = n^{1/3}$，用均值不等式可得 $B = n^{2/3}$（即 $n$ 的三分之二次方）。
最终最优复杂度为 $O(n^{5/3})$——对 $n=1e5$ 来说，实际运算次数约 $2 \times 10^8$ 次（此前计算过），而C++每秒可处理 $10^8 \sim 10^9$ 次基本运算，3秒时限完全足够。
## 结论
该思路通过“拆k、拆a”两次根号分治，将原本可能 $O(n^2)$ 的难题降到 $O(n^{5/3})$。对 $n=1e5$ 的场景，C++代码只需简单优化（如用数组替代部分哈希表、减少冗余计算），3秒内可稳定通过。
```cpp
#include <cstdio>
#include <algorithm>
#include <vector>
#include <ctime>
#include <unordered_map>
#include <cmath>
#include <vector>
static char stkk[200];
#define ve std::vector
#define up std::unordered_map
#define pb push_back
#define FOR(i,a,b) for(int i = (a);i <= (b);++i)
#define REP(i,a,b) for(int i = (a);i >= (b);--i)
typedef long long ll;
inline void output(int x){
if(!x)return putchar('0'),void();
if(x<0)x = ~x+1,putchar('-');
int top = 0;
for(;x;stkk[++top]=x%10^48,x/=10);
for(;top;putchar(stkk[top--]));
}
inline void readx(int &x){
x = 0;int y = 1;char c = getchar();
for(;c<48||c>58;c = getchar())if(c=='-')y = -1;
for(;c>=48&&c<=58;c = getchar())x = (x<<1)+(x<<3)+(c^48);
x *= y;
}
const int N = 1e5+10,AA = 50,BB = 2200;
static int T,n,V,tid,A,B;
static int k[N],b[N],a[N],f[N];
static int pk[N],pktp,pa[N],patp,ct[AA][N],tct[AA][BB];
static int xx[N],xxtp;
static ve<int> bb[AA];
static int qbb[AA];
signed main(){
freopen("summer.in","r",stdin);
freopen("summer.out","w",stdout);
// output(std::pow(N,2.0/3));
readx(tid);
readx(T),readx(n),readx(V);
FOR(i,1,n)readx(k[i]),readx(b[i]);
FOR(i,1,T)readx(a[i]);
A = std::pow(n,1.0/3),B = std::pow(n,2.0/3);
FOR(i,1,n){
if(k[i]>=A){
int v = b[i];
FOR(j,1,T){
if((v+=k[i])>V)break;
!(v%a[j])&&(++f[j]);
}
}
else xx[++xxtp] = k[pk[++pktp]=i];
}
std::sort(xx+1,xx+1+xxtp);xxtp = std::unique(xx+1,xx+1+xxtp)-xx-1;
FOR(kid,1,pktp){
int id = pk[kid];
++ct[k[id]=std::lower_bound(xx+1,xx+1+xxtp,k[id])-xx][b[id]],bb[k[id]].pb(b[id]);
}
FOR(i,1,xxtp)std::sort(bb[i].begin(),bb[i].end());
FOR(i,1,T){
if(a[i]>=B){
for(ll v = a[i],tmp;v<=V;v+=a[i]){
FOR(t,1,xxtp){
if((tmp=1ll*i*xx[t])>v)break;
f[i]+=ct[t][v-tmp];
}
}
}
else pa[++patp] = i;
}
std::sort(pa+1,pa+1+patp,[&](int x,int y){return a[x]^a[y]?a[x]<a[y]:x<y;});
a[0] = -1;
for(int i = 2,j = 1,v;i <= patp+1;++i){
if(a[pa[i]]!=a[pa[j]]){
v = a[pa[j]];
FOR(tk,1,xxtp){
qbb[tk] = bb[tk].size()-1;
FOR(tv,0,v)tct[tk][tv] = 0;
}
FOR(kid,1,pktp){
int id = pk[kid];
++tct[k[id]][b[id]%v];
}
FOR(aid,j,i-1){
int id = pa[aid];
FOR(tk,1,xxtp){
for(;~qbb[tk]&&1ll*xx[tk]*id+bb[tk][qbb[tk]]>V;--tct[tk][bb[tk][qbb[tk]--]%v]);
}
FOR(tk,1,xxtp)f[id]+=tct[tk][(v-1ll*xx[tk]*id%v)%v];
}
j = i;
}
}
FOR(i,1,T)output(f[i]),putchar(10);
return 0;
}
```