P8116题解

jxbe6666 · 2022-02-09 20:51:57 · 题解

题意：

• 给定 b 和 k，求 b 进制且保留 k 位的情况下，满足 1 \div(1 \div n)=n 的正整数 n 有多少个。

• 由于答案有多种所以要对 998244353 取模。

再讲正解之前我们先来讲一下前 50 分的获得方法。

我们可以来研究十进制下的情况。根据小学奥数老师的讲述，只有在最简分数下分母的质因数只有 2、5 的情况下才能化成有限小数。仔细一想便可以总结出规律，只有在分母的质因数是进制的因数时，才能化成有限小数。注意，找因数时，只要从 1 到 \sqrt{n} 遍历就好，在 \sqrt{n} 为整数时只能加 1。

部分代码：

    for (int i = 0; i < n; i++)
    {
        x = read();
        y = read();
        y -= 1;
        ll ans = pow(x, y);
        for (ll j = 1; j * j <= ans; j++)
        {
        if (ans % j == 0)
            if (j * j == ans)
                l += 1;
            else
                l += 2;
        }
        cout << l << '\n';
        l = 0;
    }

很显然这种方法最后 50 分会 TLE

正解：

思路分析

不难发现只要 1 \div n = \frac{1}{n} 就行了（这里的 \frac{1}n 指的是没有 k 的限制的情况下）。

整数部分自然会有一位，所以其实只能有 k-1 位小数。所以最小的一位权值为 \frac{1}{b^{k-1}}。所以无论如何这个 b 进制分数分母一定是 b^{k-1} 的约数。综上所述，我们只需求出 b^{k-1} 的约数个数就行了。

考虑将 b 质因数分解。设结果为 a_1^{p_1} \times a_2^{p_2} \cdots a_n^{p_n}。当 k-1 次方后，所有的指数都变为了原来的 k-1 倍。根据因数个数公式，就可以算出答案为 \sum\limits_{i=1} ^n p_i \times (k-1)-1。模拟即可。

AC Code：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int Mod = 998244353;
const int N = 1e6 + 5;
int z[N];
int isprime(int x)//判断质数
{
    if (x < 2)
        return 0;
    for (int i = 2; i * i <= x; i++)
        if (x % i == 0)
            return 0;
    return 1;
}
signed main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int b, k;
        cin >> b >> k;
        memset(z, 0, sizeof(z));//清空
        while (b != 1)
        {
            for (int i = 2; i <= b; i++)
            {
                if (b % i == 0 && isprime(i) == 1)
                {
                    b /= i;
                    z[i]++;
                    break;
                }
            }
        }
        int ans = 1;
        for (int i = 1; i <= N; i++)
            ans = ans * (z[i] * (k - 1) + 1) % Mod;//别忘了取模
        cout << ans << '\n';
    }
    return 0;
}