HDU 6069 Counting Divisors（区间素数筛法）

题意：。。。就题面一句话

思路：比赛一看公式，就想到要用到约数个数定理

约数个数定理就是：

对于n^k其实就是每个因子的个数乘了一个K

然后现在就变成了求每个数的每个质因子有多少个，但是比赛的时候只想到sqrt(n)的分解方法，总复杂度爆炸，就一直没过去，然后赛后看官方题解感觉好妙啊！

通过类似素数筛法的方式，把L - R的质因子给分解，就可以在O(nlogn)的时间之内把所以的数给筛出来。

代码：

/** @xigua */

#include <cstdio>

#include <cmath>

#include <iostream>

#include <algorithm>

#include <vector>

#include <stack>

#include <cstring>

#include <queue>

#include <set>

#include <string>

#include <map>

#include <climits>

#define PI acos(-1)

using namespace std;

typedef long long ll;

typedef double db;

const int maxn = 1e6 + 5;

const int mod = 998244353;

const int INF = 1e8 + 5;

const ll inf = 1e15 + 5;

const db eps = 1e-6;

bool is[maxn];

ll pri[maxn]; int cnt;

void init() {

    for (int i = 2; i < maxn; i++) {

        if (!is[i]) {

            pri[++cnt] = i; //素数筛

            for (int j = i + i; j < maxn; j += i)

                is[j] = 1;

        }

    }

}

ll fac[maxn], p[maxn];

void solve() {

    ll l, r, k; cin >> l >> r >> k;

    ll res = 0;

    //通过1 到 (r - l + 1)的数组来表示 l 到 r

    //fac代表当前数的因子个数，p代表当前数被分解之后的值

    for (ll i = l; i <= r; i++)

        fac[i-l+1] = 1, p[i-l+1] = i;

    for (int i = 1; i <= cnt; i++) {

        ll be;

        if (l % pri[i] == 0) be = l;

        else {

            be = l + (pri[i] - l % pri[i]); //找到筛法的起点，因为有些不是从l开始的

        }

        for (ll j = be; j <= r; j += pri[i]) { //枚举be到r

            //每次增加pri[i]就可以保证这个数肯定是pri[i]的倍数

            ll tmp = 0;

            while (p[j-l+1] % pri[i] == 0) {    //看当前质因数的个数

                tmp++;

                p[j-l+1] /= pri[i];

            }

            fac[j-l+1] = fac[j-l+1] * (k * tmp % mod + 1) % mod;

        }

    }

    for (ll i = l; i <= r; i++) {

         //素数

        if (p[i-l+1] != 1) fac[i-l+1] = fac[i-l+1] * (k  + 1) % mod;

        res = (res + fac[i-l+1]) % mod;

    }

    cout << res << endl;

}

int main() {

    int t = 1, cas = 1;

    //freopen("in.txt", "r", stdin);

    //freopen("out.txt", "w", stdout);

    init();

    scanf("%d", &t);

    while(t--) {

       // printf("Case %d: ", cas++);

        solve();

    }

    return 0;

}