hdu6069

hdu 6069
假设i=(p1^w1)*(p2^w2)*...这一步是质因数分解
它的因数个数为(w1+1)*(w2+1)*...
那么i^k的约数个数为(w1*k+1)*(w2*k+1)*...

如果我们对每个i都分解质因数，那么复杂度将是1e6*sqrt(1e12)的
那我们反着来，我们对每一个质数去跑区间，看区间里哪些数是这个质数的整数倍
这样保证了每次循环至少都能筛掉一个质因子，复杂度为1e6*64

#include <bits/stdc++.h>
#define inf 2333333333333333
#define N 1000010
#define p(a) putchar(a)
#define For(i,a,b) for(register long long i=a;i<=b;++i)

using namespace std;
long long T;
long long l,r,k,ans,pos,cnt,mod=998244353;
long long prime[N],a[N],z[N];//z[]是指数积
bool vis[N];

void in(long long &x){
    long long y=1;char c=getchar();x=0;
    while(c<'0'||c>'9'){if(c=='-')y=-1;c=getchar();}
    while(c<='9'&&c>='0'){ x=(x<<1)+(x<<3)+c-'0';c=getchar();}
    x*=y;
}
void o(long long x){
    if(x<0){p('-');x=-x;}
    if(x>9)o(x/10);
    p(x%10+'0');
}

void Euler(){
    for(long long i=2;i<=1e6;i++){
        if(!vis[i]) prime[++cnt]=i;
        for(long long j=1;j<=cnt&&i*prime[j]<=1e6;j++){
            vis[i*prime[j]]=1;
            if(i%prime[j]==0) break;
        }
    }
}

signed main(){
    Euler();
    in(T);
    while(T--){
        ans=0;
        in(l);in(r);in(k);
        For(i,l,r) a[i-l]=i,z[i-l]=1;
        For(i,1,cnt){
            pos=(l/prime[i]+(l%prime[i]?1:0))*prime[i];//找到第一个位置
            for(long long j=pos;j<=r;j+=prime[i]){
                long long temp=0;
                while(a[j-l]%prime[i]==0){
                    a[j-l]/=prime[i];
                    temp++;
                }
                z[j-l]*=temp*k+1;
                z[j-l]%=mod;
            }
        }
        For(i,0,r-l){//处理最后的大质数
            if(a[i]!=1){
                z[i]*=(k+1);
                z[i]%=mod;
            }
            ans+=z[i];
            ans%=mod;
        }
        o(ans);p('
');
    }
    return 0;
}