学习笔记：数论进阶（整除与约数）

前置知识：看这篇博客就好了：戳我
算是数论进阶吧（也不会太难）。

(Part;1).因子个数定理

我们考虑一个整数(a(a>1)):

[a=p_1^{k_1}p_2^{k_2}......p_n^{k_n} ]

也就是

[a=prod_{i=1}^n p_i^{k_i} ]

的约数有

[prod_{i=1}^n(k_i+1) ]

个。
证明：
我们考虑任意一个(p)，含有(p)的因子可以包括(p^0,p^1,p^2......p^k),共(k+1)种取值，那么所有的质因子的取值组合就有

[prod_{i=1}^n(k_i+1) ]

个，且互不相同。

(Part;2).整除分块（数论分块）

我们如何求:

[sumlimits_{i=1}^nleftlfloordfrac{n}{i} ight floor ]

呢？
不如手玩一下（滑稽：
比如说(n=10),可以得到一个表格：

(i)	1	2	3	4	5	6	7	8	9	10
(leftlfloordfrac{n}{i} ight floor)	10	5	3	2	2	1	1	1	1	1

好了，容易发现取(1,2)两值的数有多个，考虑把他们一下子都筛掉。
我们考虑(leftlfloordfrac{n}{i} ight floor)的实际意义是：(i)这个数对应的取值，那么容易看出(leftlfloordfrac{n}{leftlfloordfrac{n}{i} ight floor} ight floor) 代表着为(leftlfloordfrac{n}{i} ight floor)值的最后一个数，我们就可以每发现一个新得数，直接跳就好了。
代码是这样的：

ll cal(ll x)
{
	if(x==1) return 1ll*1;//注意1要特例
	ll sum=0;
	for(ll i=1;i<=x;i++)
	{
		sum+=((x/(x/i)-i+1)*(x/i))%mod;
		i=x/(x/i);
	}
	return sum%mod;
}

复杂度是多少呢？
是(O(sqrt{n}))的，
证明：
分类讨论：
1.若(ileqslant sqrt{n})，那么(leftlfloordfrac{n}{i} ight floor) 的取值只有最多(sqrt{n})种。
2.若(i<sqrt{n})，那么(leftlfloordfrac{n}{i} ight floor) 的取值也只有最多(sqrt{n})种。
综上最多只有(2sqrt{n})种取值，复杂度就是(O(sqrt{n}))的。

当然有例题了，嘿嘿。
题目链接：P3935 Calculating
观察此题，发现(f(i))不就是裸的约数个数定理吗？？？
易得：

[f(n)=sumlimits_{i=1}^nsumlimits_{d|i}^i1 ]

然而我们要求的是区间和。
设

[G(n)=sumlimits_{i=1}^nsumlimits_{d|i}^i1 ]

直接求(G(r)-G(l-1))就行了。
我们考虑对(G(n))化简。
考虑每个数的贡献，每个数(x)作为别统计的约数出现了(leftlfloordfrac{n}{x} ight floor)次。
此题得到的式子为：

[sumlimits_{i=1}^rleftlfloordfrac{r}{i} ight floor-sumlimits_{i=1}^{l-1}leftlfloordfrac{l-1}{i} ight floor ]

数论分块求即可。

(Code):

#include<cstdio>
#include<iostream> 
#include<cstring>
using namespace std;
typedef long long ll;
const int mod=998244353;
ll l,r;
ll cal(ll x)
{
	if(x==1) return 1ll*1;
	ll sum=0;
	for(ll i=1;i<=x;i++)
	{
		sum+=((x/(x/i)-i+1)*(x/i))%mod;
		i=x/(x/i);
	}
	return sum%mod;
}
int main()
{
	scanf("%lld%lld",&l,&r);
	printf("%lld
",(cal(r)-cal(l-1)+mod)%mod);
	return 0;
}

当然，在问及数论分块的板题时，更多人会说这个：
题目链接：P2261 [CQOI2007]余数求和
我们知道取模的另一种意义：

[n\%mLeftrightarrow n-mleft lfloor dfrac{n}{m} ight floor ]

那我们来化简式子吧：

[sumlimits_{i=1}^nk\%i=sumlimits_{i=1}^n(k-ileft lfloor dfrac{k}{i} ight floor)=nk-sumlimits_{i=1}^nileft lfloor dfrac{k}{i} ight floor ]

然后数论分块就好了。
不过还是需要注意一些问题的：
这里数论分块是有界的数论分块，为什么呢，我们对式子进行进一步化简：
设原式为(S(n,k)),那么：

[S(n,k)= egin{cases}nk-sumlimits_{i=1}^nileft lfloor dfrac{k}{i} ight floor&nleqslant k\nk-sumlimits_{i=1}^kileft lfloor dfrac{k}{i} ight floor&n>kend{cases} ]

为什么呢，由于当(i>k)时，(left lfloor dfrac{k}{i} ight floor=0)。
对于(nleqslant k)的情况下，要特判下一段点与边界(n)的大小比较，以免越界。
这就是提高版的数论分块。

(Code)：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define read(x) scanf("%lld",&x)
#define ll long long 
ll sum,n,k;
ll cal(ll n,ll m)
{
	ll ans=0;
	for(ll i=1;i<=m;i++)
	{
		ll r=min(m,n/(n/i));
		ans=ans+(i+r)*(r-i+1)/2*(n/i);//注意这里用到了等差数列求和公式
		i=r;
	}
	return ans;
}
int main()
{
	read(n),read(k);
	sum=n*k;
	printf("%lld
",sum-cal(k,min(n,k)));
	return 0;
}

应该能看懂吧......