【洛谷 3935】Calculating

【题目】

传送门

题目描述：

若 x x x 分解质因数结果为 x = p 1 k 1 p 2 k 2 ⋯ p n k n x=p_1^{k_1}p_2^{k_2}\cdots p_n^{k_n} x=p1k1​​p2k2​​⋯pnkn​​，令 f ( x ) = ( k 1 + 1 ) ( k 2 + 1 ) ⋯ ( k n + 1 ) f(x)=(k_1+1)(k_2+1)\cdots (k_n+1) f(x)=(k1​+1)(k2​+1)⋯(kn​+1)，求 ∑ i = l r f ( i ) \sum_{i=l}^rf(i) ∑i=lr​f(i) 对 998244353 998244353 998244353 取模的结果。

输入格式：

输入共一行，两个数， l , r l,r l,r。

输出格式：

输出共一行，一个数，为 ∑ i = l r f ( i ) \sum_{i=l}^rf(i) ∑i=lr​f(i) 对 998244353 998244353 998244353 取模的结果。

样例数据：

输入

2 4

输出

7

说明：

【分析】

分析题目，不难发现 f ( n ) f(n) f(n) 表示 n n n 的因数个数。

我们用前缀和的思想， S ( n ) = ∑ i = 1 n f ( i ) S(n)=\sum\limits_{i=1}^nf(i) S(n)=i=1∑n​f(i)，那最后的答案就是 S ( r ) − S ( l − 1 ) S(r)-S(l-1) S(r)−S(l−1)。

对于 S ( n ) S(n) S(n)，它满足下面这个性质：

S ( n ) = ∑ i = 1 n ⌊ n i ⌋ S(n)=\sum_{i=1}^n\lfloor\frac{n}{i}\rfloor S(n)=i=1∑n​⌊in​⌋

可以这样理解这个式子：我们要统计 n n n 以内的数的约数个数之和，等价于统计每个数是多少个数的约数。

那么对于一个数 i i i，显然它是 ⌊ n i ⌋ \lfloor\frac{n}{i}\rfloor ⌊in​⌋ 个数的约数，统计出和就可以了。

上面的式子就是裸的除数分块了，直接上模板就行。

时间复杂度 O ( n ) O(\sqrt n) O(n

​)。

【代码】

#include<cstdio>
#include<cstring>
#include<algorithm>
#define Mod 998244353
using namespace std;
long long solve(long long x)
{
	long long i,j,ans=0;
	for(i=1;i<=x;i=j+1)
	{
		j=x/(x/i);
		ans=(ans+(x/i)*(j-i+1)%Mod)%Mod;
	}
	return ans;
}
int main()
{
	long long l,r;
	scanf("%lld%lld",&l,&r);
	printf("%lld",(solve(r)-solve(l-1)+Mod)%Mod);
	return 0;
}