P8116

_luanyi_ · 2022-02-07 09:49:49 · 题解

题目要我们做的是，在 b 进制下，统计正整数 n 的个数，n 要满足 n' = 1 \div n 中的数码不超过 k 个，答案对 998244353 取模。

若要满足 n' = 1 \div n 数码不超过 k 个，我们应满足哪些条件？

为了满足条件 1，应满足 n 中所含质因数均为 b 的约数。
为了满足条件 2，应满足 n \leqslant b ^ {k - 1}。
综合所得，n 应满足 n | b ^ {k - 1}，即 n 为 b ^ {k - 1} 的约数。
则答案为 b ^ {k - 1} 的约数个数。
设分解质因数后 b = p_1^{m_1} \times p_2^{m_2} \times \cdots \times p_n^{m_n} ，则 b^{k-1} = p_1^{(k-1)m_1} \times p_2^{(k-1)m_2} \times \cdots \times p_n^{(k-1)m_n} ，其约数个数为 (k-1)m_1 \times (k-1)m_2 \times \cdots \times (k-1)m_n。
时间复杂度 O(T\sqrt b)，妥妥的。

#include <bits/stdc++.h>
#define fq(i,a,b) for (int i = (a); i <= (b); i++)
#define fnq(i,a,b) for (int i = (a); i < (b); i++)
#define nfq(i,a,b) for (int i = (a); i >= (b); i--)
#define nfnq(i,a,b) for (int i = (a); i > (b); i--)
#define fe(u) for (int i = head[u]; i; i = edge[i].nxt)
using namespace std;
#define int long long
inline int rd () {
    int f = 1;
    char ch = getchar ();
    while (!isdigit (ch)) (ch == '-' ? (f = -1) : 0), ch = getchar ();
    int num = 0;
    while (isdigit (ch)) num = num * 10 + ch - '0', ch = getchar ();
    return num * f;
}
#define d rd ()
const int mod = 998244353;
int T = d;
int p[10101010], cnt;
signed main () {
    while (T--) {
        int a = d, b = d - 1;
        int sq = sqrt (a); cnt = 0;
        fq (i, 2, sq) {
            if (a % i == 0) {
                p[++cnt] = 0;
                while (a % i == 0) ++p[cnt], a /= i;
            }
        } if (a > 1) p[++cnt] = 1;
        int ans = 1;
        fq (i, 1, cnt) ans = ans * (p[i] * b + 1) % mod;
        cout << ans << endl;
    }
    return 0;
}