【题目来源】
https://www.luogu.com.cn/problem/P3935
【题目描述】
若 x 分解质因数结果为 x=(p1^k1)×(p2^k2)×……×(pn^kn)，令 f(x)=(k1+1)(k2+1)⋯(kn+1)，求 ∑f(i) 对 998244353 取模的结果（其中，i=l~r）。
【输入格式】
输入只有一行两个整数，分别表示 l 和 r。
【输出格式】
输出一行一个整数表示答案。
【输入样例】
2 4
【输出样例】
7
【数据范围】
1≤l≤10^14，l≤r≤1.6×10^14，r−l>10^14。
【算法分析】
● 整数分块算法：https://blog.csdn.net/hnjzsyjyj/article/details/162819219
● 若 x=(p1^k1)×(p2^k2)×……×(pn^kn)，则 f(x)=(k1+1)(k2+1)⋯(kn+1) 实际上就是 x 的约数个数。而约数个数和的经典公式为 ∑f(i)=∑⌊n/i⌋，其中 i=1~n。
● 约数个数定理：https://blog.csdn.net/hnjzsyjyj/article/details/158127227
【算法代码】
#include <bits/stdc++.h> using namespace std; typedef long long LL; const LL MOD=998244353; LL cal(LL n) { LL t=0; for(LL le=1,ri=0; le<=n; le=ri+1) { LL k=n/le; ri=n/k; t=(t+k*((ri-le+1)%MOD))%MOD; } return t; } int main() { ios::sync_with_stdio(0); cin.tie(0); LL le,ri; cin>>le>>ri; LL ans=(cal(ri)-cal(le-1)+MOD)%MOD; cout<<ans<<"\n"; return 0; } /* in:2 4 out:7 */
【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/162819219
https://blog.csdn.net/hnjzsyjyj/article/details/158127227
