自动搬运

查看原文

来自洛谷，原作者为

	囧仙 你做东方鬼畜音MAD，好吗？

搬运于2025-08-24 22:36:10，当前版本为作者最后更新于2022-02-09 19:38:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题解

首先给出结论：

$$n''=n \iff n \mid b^{k-1}$$

考虑设 $n\in[b^s,b^{s+1})$，其中 $0\le s\le k-1$。同时，我们设 $n'$ 在计算器上被舍去的那部分的值为 $\Delta n$。先证明这样一个引理：

$$\Delta n\ge b^{-k+1}\cdot \frac{1}{n} \text{ 或者 } \Delta n=0 $$

对于第二种情况，显然是 $n\mid b^{k-1}$；对于第一种情况，我们可以类比竖式计算。如果 $n \nmid b^{k-1}$，那么我们计算到屏幕的末尾时，必然还有一个非常小的数 $t$ 还没被除去，但是 $t\ge b^{-k+1}$。此时的 $\Delta n$ 就是 $\frac{t}{n}$，因此 $\Delta n\ge b^{-k+1}\cdot \frac{1}{n}$。换言之，由于 $1=n\cdot (n'+\Delta n)=n\cdot n'+n\cdot\Delta n$，而 $n\cdot n'<1$ 且 $n\cdot n'$ 是精确到小数点后 $k-1$ 位的（在小数点 $k$ 位往后都是 $0$），那么就有 $n\cdot\Delta n=1-n\cdot n'\ge b^{-k+1}$，因而 $\Delta n\ge b^{-k+1}\cdot\frac{1}{n}$。

---

我们对 $n$ 进行了这样的变换：

$$n\to \frac{1}{n}-\Delta n\to \frac{1}{\frac{1}{n}-\Delta n}-\Delta n' $$

最终显示在屏幕上的 $n$，它右侧最多还能显示 $k-s-1$ 位。因此，一个 $n$ 不满足条件，等价于：

$$\frac{1}{\frac{1}{n}-\Delta n}\ge n+b^{1-k+s}$$

由于 $n \mid b^{k-1}$ 时，$t=0$，因此对于 $n \mid b^{k-1}$ 必然符合题意。下面证明所有 $n \nmid b^{k-1}$，都不符合题意。

想要证明 $n$ 不符合题意，就是要证明：

$$1\ge 1+\frac{1}{n}\cdot b^{1+s-k}-n\cdot\Delta n-\Delta n\cdot b^{1+s-k} $$

简单移项，可以得到：

$$n\cdot\Delta n+\Delta n\cdot b^{1+s-k}\ge \frac{1}{n}\cdot b^{1+s-k} $$

只要证明：

$$n\cdot\Delta n\ge \frac{1}{n} \cdot b^{1+s-k}$$

根据 $n\in[b^s,b^{s+1})$，以及我们证明的引理 $\Delta n\ge b^{-k+1}\cdot \frac{1}{n}$，就可以得证。于是结论成立。故所有 $n \nmid b^{k-1}$ 的 $n$ 都不满足条件。

---

现在我们知道了，$n$ 符合条件当且仅当 $n\mid b^{k-1}$，所以我们只要求出 $b^{k-1}$ 的因子数即可。我们将其质因数分解：

$$\begin{aligned} b &=\prod p_i^{c_i} \cr b^{k-1}&=\prod p_i^{c_i\cdot (k-1)} \end{aligned} $$

根据乘法原理，每个质因子的指数的取值范围是 $0\sim c_i\cdot(k-1)$ 共有 $c_i\cdot(k-1)+1$ 个。所以最终答案为：

$$\prod (c_i\cdot (k-1)+1)$$

参考代码

#include<bits/stdc++.h>
#define up(l,r,i) for(int i=l,END##i=r;i<=END##i;++i)
#define dn(r,l,i) for(int i=r,END##i=l;i>=END##i;--i)
using namespace std;
typedef long long i64;
const int INF =2147483647;
const int MOD =998244353;
int qread(){
    int w=1,c,ret;
    while((c=getchar())> '9'||c< '0') w=(c=='-'?-1:1); ret=c-'0';
    while((c=getchar())>='0'&&c<='9') ret=ret*10+c-'0';
    return ret*w;
}
int main(){
    up(1,qread(),T){
        int b=qread(),k=qread(),ans=1;
        if(k==1){puts("1");continue;}
        for(int i=2;i*i<=b;++i){
            int c=0; while(b%i==0) ++c,b/=i; ans=1ll*ans*((k-1)*c+1)%MOD;
        }
        if(b!=1) ans=1ll*ans*k%MOD; printf("%lld\n",ans);
    }
    return 0;
}