题解 P8116 【「Wdoi-1.5」魔理沙的计算器】

· · 题解

题解

首先给出结论：

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;
}