只会写60分算法QuQ

考虑到一个数$x$大于$\sqrt{x}$的质因数最多只有一个，我们可以筛出小于$\sqrt{r}$范围内的所有质因数然后直接用这些取分解质因数。

最后扫一遍发现还没有分解完的就累计到答案中去。

所有下标向左平移$l$位。

时间复杂度 $O(√r+ (r−l+ 1)loglog(r−l+ 1))$

Code：

#include 
      
       #include 
       
        using namespace std;typedef long long ll;const int N = 1e6 + 5;const ll P = 998244353LL;ll a, b, k, pCnt = 0, pri[N / 10LL], f[N], g[N];bool np[N];inline void sieve() {    for(ll i = 2; i <= N; i++) {        if(!np[i]) pri[++pCnt] = i;        for(ll j = 1; j <= pCnt && pri[j] * i <= N; j++) {            np[i * pri[j]] = 1;            if(i % pri[j] == 0LL) break;        }    }}int main() {    scanf("%lld%lld%lld", &a, &b, &k);    sieve();    for(ll i = a; i <= b; i++) f[i - a] = i, g[i - a] = 1LL;    for(ll i = 1; i <= pCnt; i++) {        if(pri[i] * pri[i] > b) break;        for(ll j = (a / pri[i]) * pri[i]; j <= b; j += pri[i]) {            if(j < a) continue;             ll t = 0;            for(; f[j - a] % pri[i] == 0LL; f[j - a] /= pri[i], t++);            g[j - a] = g[j - a] * (t * k + 1LL) % P;        }    }    for(ll i = a; i <= b; i++)        if(f[i - a] != 1LL)             g[i - a] = (g[i - a] * (k + 1LL)) % P;        ll ans = 0LL;    for(ll i = a; i <= b; i++)         (ans += g[i - a]) %= P;    printf("%lld\n", ans);        return 0;}