Counting Divisors HDU - 6069

In mathematics, the function d(n) denotes the number of divisors of positive integer n .

For example, d(12)=6 because 1,2,3,4,6,12 are all 12 's divisors. In this problem, given l,r and k , your task is to calculate the following thing : (∑i=lrd(ik))mod998244353 Input The first line of the input contains an integer T(1≤T≤15) , denoting the number of test cases. In each test case, there are 3 integers l,r,k(1≤l≤r≤1012,r−l≤106,1≤k≤107) . Output For each test case, print a single line containing an integer, denoting the answer. Sample Input 3 1 5 1 1 10 2 1 100 3 Sample Output

10

48

2302

题目分析：求区间 [ l , r ]中的所有数的k次幂因子的个数和模 998244353的值。

知识储备：对任意一个自然数都可以唯一分解为:   n=pα11⋅pα22⋯pαss   其中 pi 为素数。

         数n的因子个数函数：   τ(n)=∏si=0(αi+1)   其中  αi  为上述分解中  pi  的幂。本题中的 k 方很好处理，只要每个 α 都乘一下 k 就可以了。

题目分析：比赛的时候采用的方法是一个数一个数的进行素因子分解，求出每个数的k次幂的因数和，再相加，结果超时了，意料之中。

                看标程给的思路主要是通过素因子来找数，看那些数是这些素因子的倍数，求出每个素因子的幂，然后求和。

下面给出求一个数因子和的一般代码：

int count(int n)///求n的因子的个数 { int s=1; for(int i=2;i*i<=n;i++) if(n%i==0) { int a=0; while(n%i==0) { a++; n/=i; } s=s*(a+1); } if(n>1) s=s*2; return s; } 给出AC代码：

#include<cstdio> #include<iostream> #include<cstring> using namespace std; const int N=1e6+9; const int mod=998244353; bool isprime[N]; int cnt=0;///记录素数的个数 long long prime[N]; void doprime()///线性筛素数，打表 { memset(isprime,true,sizeof(isprime)); isprime[0]=isprime[1]=false; for(int i=2;i<=N;i++) if(isprime[i]) { prime[cnt++]=i; for(long long j=i+i;j<=N;j+=i) isprime[j]=false; } } long long l,r,k; long long n; long long f[N]; long long num[N];///每个数的因子的个数 void work(long long p) { for(long long i=l/p*p;i<=r;i+=p) if(i>=l) { if(f[i-l]%p==0) { int a=0; while(f[i-l]%p==0) { f[i-l]/=p; a++; } num[i-l]=num[i-l]*((long long)a*k+1)%mod; } } } int main() { doprime(); int t; scanf("%d",&t); while(t--) { scanf("%lld%lld%lld",&l,&r,&k); n=r-l; ///区间长度 long long ans=0; for(int i=0;i<=n;i++) { f[i]=i+l; num[i]=1; } for(int i=0;i<cnt;i++) { if(prime[i]*prime[i]>r) break; work(prime[i]); } for(int i=0;i<=n;i++) { if(f[i]>1) num[i]=num[i]*(k+1)%mod; ans=(ans+num[i])%mod; } printf("%lld\n",ans); } return 0; }