P8116 「Wdoi-1.5」魔理沙的计算器 题解
Published:
P8116 「Wdoi-1.5」魔理沙的计算器 题解
题意简述
使用 $b$ 进制、屏幕能显示 $k$ 个数字、使用去尾法保留小数的计算器，计算了 $1\div n=n’$，再计算 $1\div n’=n’’$。求有多少个正整数 $n$ 使得 $n=n’’$。
答案对 $998,244,353$ 取模。
$2\le b\le 10^5$，$1\le k\le 500$。
解法
$\div$ 是题目中的除法。有 $1 \div n = \dfrac 1 {b^{k-1}} \left\lfloor \dfrac {b^{k-1}} n \right\rfloor$。
设 $a = b^{k-1}$：
\[\begin{aligned} & 1 \div (1 \div n) \\ =& \dfrac 1 a \left\lfloor \dfrac a {\frac 1 a \left\lfloor \frac a n \right\rfloor} \right\rfloor \\ =& \dfrac 1 a \left\lfloor \dfrac {a^2} {\left\lfloor \frac a n \right\rfloor} \right\rfloor \end{aligned}\]问题变为解方程：$\left\lfloor \dfrac {a^2} {\left\lfloor \frac a n \right\rfloor} \right\rfloor = a \times n$。
事情进行到这里似乎卡住了，这时不妨用 Python 打个表找下规律。
a = int(input())
print(f"a={a}")
ans = 0
for n in range(1, a+1):
if (a * a) // (a // n) == a * n:
ans += 1
print(f"n={n}")
print(ans)
当输入 $a = 114514$ 时，输出为：
a=114514
n=1
n=2
n=31
n=62
n=1847
n=3694
n=57257
n=114514
8
| 不难发现，方程的解似乎就是全部 $a$ 的因数，即 $n | a$。解的个数即为 $d(a) = d(b^{k-1})$。 |
发现这个结论之后就可以开始写代码了。
对结论的证明
| 证明命题：$\left\lfloor \dfrac {a^2} {\left\lfloor \frac a n \right\rfloor} \right\rfloor = a \times n$ 的充要条件是 $n | a$。 |
右推左简单。接下来证明左推右：
设 $a = kn+b$，其中 $k = \left\lfloor \dfrac a n \right\rfloor$。（$b,k$ 不是题目中的 $b,k$，撞变量名了）
把 $a = kn+b$ 代入 $\left\lfloor \dfrac {a^2} {\left\lfloor \frac a n \right\rfloor} \right\rfloor = a \times n$：
\[\left\lfloor kn^2 + 2bn + \dfrac {b^2} k \right\rfloor = kn^2 + bn\]由于 $kn^2 + bn$ 是整数，可以把它从左边提出来：
\[\left\lfloor bn + \dfrac {b^2} k \right\rfloor = 0\]| 由于 $bn$ 为自然数，要使得它为 $0$ 只能 $b = 0$。即 $n | a$。 |
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 998'244'353;
int main() { ios::sync_with_stdio(0); cin.tie(0);
int T; cin >> T; while (T--) {
ll b, k; cin >> b >> k;
ll ans = 1;
for (ll d = 2; d * d <= b; d++)
if (b % d == 0) {
ll e = 0;
while (b % d == 0) {
e++;
b /= d;
}
(ans *= (e * (k-1) + 1)) %= MOD;
}
if (b != 1)
(ans *= k) %= MOD;
cout << ans << '\n';
}
return 0;
}