HDU-6069: Counting Divisors （素筛 + 思维）

数论

---

Problem Description

In mathematics, the function d(n) denotes the number of divisors of positive integer n.

For example, d(12)=6 because 1,2,3,4,6,12 are all 12's divisors.

In this problem, given l,r and k, your task is to calculate the following thing :

$$\begin{eqnarray*} \left(\sum_{i=l}^r d(i^k)\right)\bmod 998244353 \end{eqnarray*}$$

Input

The first line of the input contains an integer T(1≤T≤15), denoting the number of test cases.

In each test case, there are 3 integers $l,r,k(1≤l≤r≤10^{12},r−l≤10^6,1≤k≤10^7)$.

Output

For each test case, print a single line containing an integer, denoting the answer.

Sample Input

3
1 5 1
1 10 2
1 100 3

Sample Output

10
48
2302

---

题意：规定d(i)表示数字i的因子个数为多少，如i等于12，那么d(i)就等于6，因为12的因子有1，2，3，4，6，12。题目输入l，r，k，意思是在l到r的区间里的每个数为n，求$d（n^k）$，累加起来即可。

分析：一个数的因子个数：将这个数质因子分解后，每个质因子的指数加一乘起来即为答案。比如$12=2^2+3^1$，$(2+1)*(1+1)=6$。题中求$d(n^k)=(kc_1+1)(kc_2+1)...(kc_m+1)$，又因为一个数n的因子除了自己本身之外，其他质因子一定不超过$\sqrt n$，因此只需要将小于$10^6$的素数求出。然后，对于$[l,r]$区间的每一个数，如果依次枚举将其质因子分解，则会超时。那么我们枚举质因子，能够整除质因子的数只有$[l,r]$区间里该质因子的倍数，因此就可以跳着枚举。最后剩下的部分就是超过$\sqrt{r}$的质数，只可能是0个或1个。

---

• 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e6 + 5;
const int mod = 998244353;
int prime[maxn];
LL num[maxn], ans[maxn];
void primeform (int n)
{
    prime[0] = 2;
    int cnt = 1;
    for (int i = 3; i < n; i++)
    {
        int flag = 1;
        for (int j = 2; j * j <= i; j++)
            if (i % j == 0)
            {
                flag = 0;
                break;
            }
        if (flag) prime[cnt++] = i;
    }
}
void getans (LL l, LL r, LL k)
{
    for (int i = 0; prime[i] <= r && prime[i]; i++)
    {
        LL now = l % prime[i] == 0 ? 0 : prime[i] - l % prime[i]; //找到起点
        for (LL j = now; j <= r - l; j += prime[i])
        {
            LL cnt = 0;
            while (num[j] % prime[i] == 0)
            {
                num[j] /= prime[i];
                cnt++;
            }
            ans[j] = (ans[j] * ( (cnt * k + 1) % mod) ) % mod;
        }
    }
    for (int i = 0; i <= r - l; i++) //超过根号r的质因子
        if (num[i] != 1)
        ans[i] = (ans[i] * (k + 1)) % mod;
}
void clr(LL l, LL r)
{
    for (int i = 0; i <= r - l; i++)
        ans[i] = 1, num[i] = i + l;
}
int main()
{
    primeform (1e6);
    int t;
    scanf ("%d", &t);
    while (t--)
    {
        LL l, r, k, ret = 0;
        scanf ("%lld %lld %lld", &l, &r, &k);
        clr(l, r);
        getans (l, r, k);
        for (int i = 0; i <= r - l; i++)
            ret = (ret + ans[i]) % mod;
        printf ("%lld\n", ret);
    }
    return 0;
}