2017年多校联训赛Team 4-hdu6069如何高效计算一个数的所有约数？

本文共计868个文字，预计阅读时间需要4分钟。

题目：传递门问题解题：根据约数定理，设\( n=p_1^{a_1} \times p_2^{a_2} \times p_3^{a_3} \times \ldots \times p_k^{a_k} \)，\( n \)的约数的个数为\((a_1+1)(a_2+1)(a_3+1)\ldots(a_k+1)\)。若\( i=p_1^{a_1} \times p_2^{a_2} \times p_3^{a_3} \times \ldots \times p_k^{a_k} \)，则\( i \)在\( n \)中的倍数个数为\( i \div K \)。

​​题目传送门​​

题解：
根据约数个数定理：​​​n=p1^a1×p2^a2×p3^a3*…*pk^ak​​​,n的约数的个数就是(a1+1)(a2+1)(a3+1)…(ak+1).
若​​​i=p1^a1×p2^a2×p3^a3*…*pk^ak​​​,则​​i^K=p1^(a1*K)×p2^(a2*K)×p3^(a3*K)*…*pk^(ak*K)​​​,​​i^K​​​的约数的个数就是​​(a1*K+1)(a2*K+1)(a3*K+1)…(ak*K+1)​​​ 但是题目重点转换为​​L~R​​的因数个数和，也就是重点转换为​​L~R​​的质因数分解，两次塞选，第一次塞出1e6以内的所有质数，第二次枚举区间[L,R]中之前塞选得到质数的倍数，剩下的就是[L,R]的质数，用cnt数组记录它们因数的个数，因为L和R比较大，所以再开一个数组存储它们的值，所以cnt[i]就可以相当于cnt[i+L]。
要用long long，不然中间会爆int。

AC代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
typedef long long ll;
using namespace std;
const int maxn=1e6+10;
const int mod=998244353;
int tot,t;
ll l,r,k,ans,cnt[maxn],q[maxn],prime[maxn];
bool vis[maxn];
void init(){
for(int i=2;i<maxn;i++){
if(!vis[i])
prime[tot++]=i;
for(int j=0;j<tot&&i*prime[j]<maxn;j++)
{
vis[i*prime[j]]=1;
if(!(i%prime[j]))
break;
}
}
}//快速素数筛
int main(){
scanf("%d",&t);
init();
while(t--)
{
scanf("%lld%lld%lld",&l,&r,&k);
ans=0;
if(l==1)//1它只有一个因数（自己）比较独特，特判一下
ans++,l++;
/*所以ans+=1,l->2（一定要变成2，不然wa,不过也可以改后面的代码，也可ac,比较麻烦）*/
for(ll i=0;i<=r-l;i++)
cnt[i]=1,q[i]=l+i;
for(ll i=0;prime[i]*prime[i]<=r;i++)
{
ll j=l/prime[i]+(l%prime[i]!=0);
for(j=j*prime[i];j<=r;j+=prime[i])
{
ll tmp=0;
while(q[j-l]%prime[i]==0)
q[j-l]/=prime[i],tmp++;
cnt[j-l]*=(tmp*k+1)%mod,cnt[j-l]%=mod;
}
}//将l-r的非质数进行分解，分解成质因数
for(ll i=0;i<=r-l;i++)
{
if(q[i]!=1)
ans+=((k+1)*cnt[i])%mod;
/*(1）i为素数时
(2）i为非素数,但在上面分解成质因数时，q[i]!=1,所以最后q[i]一定是一个素数所以结合（1）（2）最后是乘（k*1+1）=(k+1)*/
else
ans+=cnt[i];
ans%=mod;
}
printf("%lld\n",ans);
}
}