题目的意思是:给出l,r, k,求l到r区间内每个数的k次方的约数个数的和,再对998244353取余。

这题用到的技巧还真是多啊,乱搞暴力肯定GG。


首先我们来看看怎么求解约数的个数。一个数可以分解成多个质数的的乘积。假设p为质数(1不是质数啊,怎么每次都讲不听呢),所以有:

n = p1^c1*p2^c2*p3^c3*......*pm^cm

根据乘法原理:n的约数的个数就是(c1+1)(c2+1)(c3+1)…(cm+1)。所以:


d(n) = (c1+1)(c2+1)(c3+1)…(ck+1)

d(n^k) = (k*c1+1)(k*c2+1)(k*c3+1)…(k*cm+1)

本以为通过素数筛法筛了素数之后对l-r区间内每个数进行素数分解就OK了,没想到还是TLE了。这里要用到一个技巧,因为我们直接对区间的数进行分解的话,当一个数是很大的质数时就会增加很多不必要的计算判断,所以我们要将质数乘以一定的倍数使它增长到区间内,如果倍数在区间内那么直接将区间内的数分解即可,之后再以当前质数的一倍递增,这样就可以分解完区间内所有能被当前质数分解的数。并且质数之积肯定是小于等于r的。


通过上面的方法分解完成后循环一遍将每个数的d(n^k)%mod加起来取模即可。

说的可能有点繁琐,具体请看代码。


地址:http://acm.hdu.edu.cn/showproblem.php?pid=6069


代码:

StatusAccepted
Time2732ms
Memory25984kB
Length1892
LangC++


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
using namespace std;
#define lowbit(x) ((x)&(-x))
#define INF 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
#define    GE() printf(">----------\n")
#define    IN() freopen("in.txt","r",stdin)
#define    OUT() freopen("out.txt","w",stdout)
#define MP pair<int, int>
typedef long long LL;
const int mod=998244353;
const int inf=0x3f3f3f3f;
const double pi=acos(-1.0);
const double eps=1e-8;
const int maxn=1000005;
int t;
LL l, r, k, ans;
LL prime[maxn], vis[maxn], cp;
LL cnt[maxn], num[maxn], tot;
void Prime(){                        //快速素数筛法,普通素数筛法也能过,这个题我用两种筛法时间差不了多少
    mem(vis, 0),cp=0;
    for(int i=2;i<maxn;i++){
        if(!vis[i])prime[cp++]=i;
        for(int j=0;j<cp&&i<maxn/prime[j];j++){
            vis[i*prime[j]]=1;
            if(i%prime[j]==0)break;
        }
    }
}
int main()
{
    Prime();
    scanf("%d", &t);
    while(t--){
        scanf("%lld%lld%lld", &l, &r, &k);
        ans=0;
        if(l==1)ans=1, l++;
        tot=r-l+1;
        for(int i=0;i<tot;i++){
            num[i]=l+i;         //暂存l-r区间数
            cnt[i]=1;           //初始化为1,统计每个数的d(nk)
        }
        for(int i=0;prime[i]*prime[i]<=r;i++){      //遍历区间内所有质数
            LL now=ceil(l*1.0/prime[i])*prime[i];       //计算质数最低开始数
            for(now;now<=r;now+=prime[i]){          //质数递增
                LL c=0;
                while(num[now-l]%prime[i]==0){      //区间数分解
                    num[now-l]/=prime[i];
                    c++;
                }
                cnt[now-l]*=(k*c+1)%mod;
                cnt[now-l]%=mod;
            }
        }
        for(int i=0;i<tot;i++){
            if(num[i]!=1)ans+=(cnt[i]*(k+1))%mod;
            else ans+=cnt[i];
            ans%=mod;
        }
        printf("%lld\n", ans);
    }
    return 0;
}