2023.08.21 模拟赛B题

发布时间 2023-12-08 07:40:07作者: Imcaigou

LINK

水题,很难评,有一车人做出来(悲。

前置知识:数论分块

所以我们分析这个题,会发现 \(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;
}