水题,很难评,有一车人做出来(悲。
前置知识:数论分块
所以我们分析这个题,会发现 \(c=ab\) 这个条件很难入手,所以考虑怎么在这上面做一些变化。
所以想到用差分。
记 \(f(x)\) 表示钦定 \(c=x\) 时,满足 \(ab = c\) 的 \((a,b)\) 二元组个数。
记 \(g(x)\) 表示钦定 \(c = x\) 时,满足 \(ab \leq c\) 的 \((a,b)\) 二元组个数。
然后因为 \(a,b\) 的选取除了上述条件之外没有其他与 \(x,c\) 相关的限制,所以有:
\[f(x) = \Delta g(x)
\]
(说人话:
\[g(x) - g(x - 1) = f(x)
\]
正好答案求的是:
\[\sum_{i=minc}^{maxc} f(i)
\]
所以这里有两种解释方法,第一种是裂项(差分):
\[\begin{aligned}
\sum_{i=minc}^{maxc} f(i) & = \sum_{i=minc}^{maxc} (g(i) - g(i - 1)) \\
& = \sum_{i=minc}^{maxc} g(i) - \sum_{i = minc - 1}^{maxc - 1} g(i) \\
& = g(maxc) - g(minc - 1)
\end{aligned}
\]
第二种是直接上有限微积分:(?
\[\begin{aligned}
\sum_{i=minc}^{maxc} f(i) & = \sum_{minc}^{maxc} f(x)\delta x \\
& = \sum_{minc}^{maxc} \Delta g(x) \delta x \\
& = g(maxc) - g(minc - 1)
\end{aligned}
\]
(好吧其实两种解释都是有限微积分相关的)
然后就只需要设计一个算法可以对任意 \(c\) 求 \(g(c)\) 对吧。
然后我们会发现因为此时的要求变为 \(ab \leq c\) ,相当于对于任意 \(a\) 要求 \(b \leq \lfloor \frac{c}{a} \rfloor\)。
根据给的数论分块链接可知 \(\lfloor \frac{c}{a} \rfloor\) 最多只有 \(2\sqrt{c}\) 个取值,所以对于每个不同的取值可以直接枚举,求可行的 \(b\) 的个数即可。
(注意这里可行的 \(b\) 一定会取 \([minb,\min(maxb, \lfloor \frac{c}{a} \rfloor)]\) ,所以可能存在无可行 \(b\) 的情况)
#define int long long
int g (int c){
if (c < 1)
return 0;
int Cnt = 0;
for (int ia = mina;ia <= maxa && ia <= c;++ ia){
int rpos = min (c / (c / ia), maxa);
Cnt += (rpos - ia + 1) * max (min (c / ia, maxb) - minb + 1, 0ll);
ia = rpos;
}
return Cnt;
}