hdu6069(简单数学+区间素数筛法)

题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=6069

题意: 给出 l, r, k．求：(lambda d(i^k))mod998244353，其中 l <= i <= r, d(i) 为 i 的因子个数．

思路：若 x 分解成质因子乘积的形式为 x = p1^a1 * p2^a2 * ... * pn^an，那么 d(x) = (a1 + 1) * (a2 + 1) * ... * (an + 1) .显然 d(x^k) = (a1 * k + 1) * (a2 * k + 1) * ... * (an * k + 1) .

但如果仅仅以此暴力求解的话是会 tle 的, 需要用下区间素数筛法并且在筛选区间内合数时将其质因分解，将 i 对答案的贡献存储到 sum 数组中，然后再遍历一次统计素数对答案的贡献并将所有贡献累加起来即可．

代码：

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 #define ll long long

 using namespace std;

 const int MAXN = 1e6 + ;

 const int mode = ;

 int prime[MAXN], tag[MAXN], tot;

 ll sum[MAXN], gel[MAXN];

 void get_prime(void){

     for(int i = ; i < MAXN; i++){

         if(!tag[i]){

             prime[tot++] = i;

             for(int j = ; j * i < MAXN; j++){

                 tag[j * i] = ;

             }

         }

     }

 }

 ll Max(ll a, ll b){

     return a > b ? a : b;

 }

 int main(void){

     get_prime();

     ll l, r;

     int k, t;

     scanf("%d", &t);

     while(t--){

         scanf("%lld%lld%d", &l, &r, &k);

         for(int i = ; i <= r - l; i++){

             sum[i] = ; //sum[i]记录i+l对答案的贡献

             gel[i] = i + l; //将所有元素放到a数组里

         }

         for(int i = ; i < tot; i++){

             ll a = (l + prime[i] - ) / prime[i] * prime[i];

             for(ll j = a; j <= r; j += prime[i]){ // 筛[l, r]内的合数

                 ll cnt = ;

                 while(gel[j - l] % prime[i] == ){

                     cnt++;

                     gel[j - l] /= prime[i];

                 }

                 sum[j - l] = sum[j - l] * (cnt * k +  % mode);

                 if(sum[j - l] >= mode) sum[j - l] %= mode;

             }

         }

         ll sol = ;

         for(int i = ; i <= r - l; i++){

             if(gel[i] != ) sum[i] = sum[i] * (k + );

             sol += sum[i];

             if(sol >= mode) sol %= mode;

         }

         printf("%lld\n", sol);

     }

     return ;

 }

(∑i=lrd(ik))mod998244353