WOJ 41 约数统计

只会写60分算法QuQ

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

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

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

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

Code：

#include <cstdio>

#include <cstring>

using namespace std;

typedef long long ll;

const int N = 1e6 + ;

const ll P = 998244353LL;

ll a, b, k, pCnt = , pri[N / 10LL], f[N], g[N];

bool np[N];

inline void sieve() {

    for(ll i = ; i <= N; i++) {

        if(!np[i]) pri[++pCnt] = i;

        for(ll j = ; j <= pCnt && pri[j] * i <= N; j++) {

            np[i * pri[j]] = ;

            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 = ; 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 = ;

            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 ;

}

巴特西

WOJ 41 约数统计

最新文章

热门文章