1 条题解

  • 0
    @ 2024-12-30 19:15:40

    根据 CSP-S1 2023 阅读程序 B 篇,我们可以分别计算 1r1 \sim r 成为因数的次数再求和,这种算法只需要计算 rr 次。上个整除分块就能做到 O(r)O(\sqrt{r}) 了。

    #include <bits/stdc++.h>
    #define int __int128
    using namespace std;
    const long long P = 998244353;
    long long f(int n)
    {
        if(!n) return 0;
        int ans = n * (n + 1);
        for (int i = 1; (n / i) * (n / i) > n; i++)
            ans -= i * (n / i);
        for (int i = 1; i * i <= n; i++)
            ans -= i * ((n / i) + (n / (i + 1) + 1)) * (n / i - n / (i + 1)) / 2;
        return ans % P;
    }
    signed main()
    {
    	long long l, r;
        cin >> l >> r;
        cout << (f(r) + P - f(l - 1)) % P << endl;
    	return 0;
    }
    
    • 1

    信息

    ID
    99
    时间
    5000ms
    内存
    8MiB
    难度
    4
    标签
    递交数
    2
    已通过
    1
    上传者