- P54's solution
P54's Solution
- 2025-9-4 21:59:42 @
根据 CSP-S1 2023 阅读程序 B 篇,我们可以分别计算 成为因数的次数再求和,这种算法只需要计算 次。上个整除分块就能做到 了。
#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;
}