资讯详情

​【题目来源】
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
 

​