[洛谷P3935]Calculating

题目大意：设把$x$分解质因数的结果为$x=p_1^{k_1}p_2^{k_2}\cdots p_n^{k_n}$，令$f(x)=(k_1+1)(k_2+1)\cdots (k_n+1)$，求$\sum\limits_{i=l}^r f(i)(1\leqslant l\leqslant 10^{14},1\leqslant r\leqslant 1.6\times10^{14},r-l>10^{14}$

题解：可知$f(x)$为$x$的因数个数，可以把$\sum\limits_{i=l}^rf(i)$拆成$\sum\limits_{i=1}^rf(i)-\sum\limits_{i=1}^lf(i)$。
$$
\def\dsum{\displaystyle\sum\limits}
\def\dprod{\displaystyle\prod\limits}
\begin{align*}
f(p)&=\dprod_{i=1}^n(k_{p,i}+1)\\
&=\dsum_{i=1}^n[i|p]\\
\end{align*}\\
带回原式
$$

$$
\def\dsum{\displaystyle\sum\limits}
\def\dprod{\displaystyle\prod\limits}
\begin{align*}
令g(p)&=\dsum_{x=1}^pf(x)\\
&=\dsum_{x=1}^p\dsum_{i=1}^x[i|x]\\
&=\dsum_{i=1}^p\big\lfloor\dfrac p i\big\rfloor\\
\end{align*}
$$

整除分块即可。

卡点：1.读入时忘记开$long\;long$

C++ Code：

#include <cstdio>

using namespace std;

const int mod = 998244353;

long long l, r;

long long solve(long long n) {

    long long ans = 0, l, r;

    for (l = 1; l <= n; l = r + 1) {

        r = n / (n / l);

        ans = (ans + (r - (l - 1)) * (n / l)) % mod;

    }

    return ans;

}

int main() {

    scanf("%lld%lld", &l, &r);

    printf("%lld\n", (solve(r) - solve(l - 1) + mod) % mod);

    return 0;

}

巴特西

[洛谷P3935]Calculating

最新文章

热门文章