HDU 6069 求区间[L,R]每个数的k次方的因子数之和

缺乏知识点     

1.约数定理： num=p1^c1 * p2^c2 * ....* pn^cn    p代表素数   c代表对应幂次

                num对应的因子数= (c1+1)*(c2+1)*......*(cn+1)

2.一个数num   大于sqrt(num)的素因子    数量  只能 为0或者1 

可以解决的问题：

1.所有求一个数num的因子数时 只需要枚举<=sqrt(num)的素数，num除掉所有<=sqrt(num)的素数时，num！=1就说明存在一个> sqrt(num) 的素数 ，之后套约数定理算就可以了

2.如果求一个数num^k的因子数，方法同1一样，只不过套公式的时候 num^k=p1^(k*c1)  *  p2^(k*c2 )   * ....*   pn^(k*cn )

3.如果求一个区间的因子数，先把sqrt(区间上限)  的素数表打出来  ，枚举素数，再倍增枚举素数对应区间的数，然后就和上面的操作一样了。

此题官方题解

1003. Counting Divisors

设n=p_1^{c_1}p_2^{c_2}...p_m^{c_m}n=p​1​c​1​​​​p​2​c​2​​​​...p​m​c​m​​​​，则d(n^k)=(kc_1+1)(kc_2+1)...(kc_m+1)d(n​k​​)=(kc​1​​+1)(kc​2​​+1)...(kc​m​​+1)。

枚举不超过\sqrt{r}√​r​​​的所有质数$p$，再枚举区间$[l,r]$中所有$p$的倍数，将其分解质因数，最后剩下的部分就是超过\sqrt{r}√​r​​​的质数，只可能是$0$个或$1$个。

时间复杂度O(\sqrt{r}+(r-l+1)\log\log(r-l+1))O(√​r​​​+(r−l+1)loglog(r−l+1))。

#pragma comment(linker, "/STACK:1024000000,1024000000") #include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <string> #include <cstdio> #include <climits> #include <cmath> #include <vector> #include <set> #include <queue> #include <stack> #include <map> #include <sstream> #define INF 0x3f3f3f3f #define LL long long #define fora(i,a,n) for(int i=a;i<=n;i++) #define fors(i,n,a) for(int i=n;i>=a;i--) #define sci(x) scanf("%d",&x) #define scl(x) scanf("%lld",&x) const int MAXN=1000024; const long long MOD=998244353; const double eps = 1e-8; using namespace std; int t; LL l,r,k; bool npm[MAXN]; LL pm[MAXN],z=0; LL Num[MAXN],f[MAXN]; void reset(){ fill(Num,Num+MAXN,1); } int main() { #ifdef local freopen("ini.txt", "r", stdin); //freopen("out.txt","w",stdout); #endif npm[0]=npm[1]=1; for(int i=2;i<=1000000/2;i++) if(npm[i]==0){ for(int j=i+i;j<=1000000;j+=i){ npm[j]=1; } pm[z++]=i; } sci(t); while(t--){ reset(); scanf("%lld%lld%lld",&l,&r,&k); for(int i=0;i+l<=r;i++) f[i]=i+l; LL s; LL sum=0,num=0; for(int i=0;i<z;i++){ if(l%pm[i]) s=(pm[i]-l%pm[i])+l; else s=l; for(;s<=r;s+=pm[i]){ num=0; while(f[s-l]%pm[i]==0) f[s-l]/=pm[i],num++; Num[s-l]=(Num[s-l]*(num*k%MOD+1))%MOD; } } for(int i=0;i<=r-l;i++) if(f[i]==1) sum=(sum+Num[i])%MOD; else sum=(sum+Num[i]*(k+1)%MOD)%MOD; printf("%lld\n",sum); } return 0; }