P8116 「Wdoi-1.5」魔理沙的计算器

题目背景

魔理沙是普通而平凡的魔法使。在解决了大大小小的异变后，她终于攒足了足够多的钱在香霖堂里购置了一台 $\text{Carno}$ 计算器，用来计算魔女之汤各种配料的含量之比。

魔理沙早就听闻灵梦通过河童重工网络入手了一部 $\text{Casio}$ 计算器，来计算神社的香火钱，却买到了假货，最多只能显示整数部分（下取整）。而魔理沙的这部可以精确到小数点后面若干位（下取整）的计算器。更高级的是，这部计算器还可以支持其他的进制，其强大的功能高出了灵梦一大截。因此作为灵梦真挚的朋友，魔理沙希望向灵梦表达真挚的遗憾之情。

正当魔理沙打算出发之时，她发现虽然 $\text{Carno}$ 计算器不会导致一些特别大的误差，但是在计算除法时仍然会出现一定的问题。考虑将计算器的进制调整为 $10$ 进制，而计算器屏幕上最多可以显示 $5$ 位数字（小数点不计入显示位数）。比如，魔理沙希望计算 $1÷3$ 的值，那么真正显示在屏幕上的则是：

$$0.3333$$

按照道理上来讲，$1÷(1÷3)$ 结果应当等于 $3$。但出乎意料的是，当魔理沙输入 $1÷0.3333$ 后，得到的结果却是：

$$3.0003$$

这当然只是一个个例。当魔理沙计算 $1÷(1÷4)$ 时，屏幕上显示出了正确的数字。

为了防止在表达遗憾之情的时候自己的计算器也出了漏子，魔理沙希望找到有多少个数字使得计算出的结果是正确的，因此她向你求助了。

题目描述

魔理沙的计算器可以进行 $b$ 进制的运算，屏幕上可以显示 $k$ 个数字（不包含小数点）。进行计算后，若某个数字超出了屏幕，就会被直接舍去（例如 $b=10$ 时 $1÷7=0.142857\cdots$，若屏幕大小为 $4$，那么最终显示为 $0.142$）。

魔理沙用计算器计算了 $1÷n=n^{\prime }$，再计算 $1÷n^{\prime }=n^{\prime \prime }$（$n^{\prime }$ 和 $n^{\prime \prime }$ 均为显示在屏幕上的结果）。魔理沙希望知道，有多少个正整数 $n$ 使得 $n=n^{\prime \prime }$。你只需要输出这个答案对 $998,244,353$ 取模后的结果即可。

输入格式

• 第一行有一个正整数 $T$，表示数据组数。
• 接下来 $T$ 行，每行有两个正整数 $b,k$，分别表示计算器的进制、屏幕上能显示的数字个数。

输出格式

• 输出共 $T$ 行。
• 每行输出一个整数。第 $i$ 行的整数表示第 $i$ 组数据中合法的 $n$ 的总数对 $998,244,353$ 取模后的结果。

输入输出样例 #1

输入 #1

3
4 2
5 3
12 99

输出 #1

3
3
19503

说明/提示

样例解释

• 对于第一组询问，符合条件的数（转换成十进制）为 $1,2,4$。
• 对于第二组询问，符合条件的数（转换成十进制）为 $1,5,25$。

数据范围及约定

$$\begin{array}{cccccc}\text{subtask}& \text{分值}& \mathbf{b}\le & \mathbf{k}\le & \text{特殊性质}& \text{subtask 依赖}\\ 1& 20& 10& 7& -& -\\ 2& 20& 10^5& 2& k=2& -\\ 3& 10& 10^5& 3& k=3& -\\ 4& 50& 10^5& 500& -& 1,2,3\end{array}$$

对于 $100\%$ 的数据，满足 $1\le T\le 10$，$2\le b\le 10^5$，$1\le k\le 500$。

C++实现

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

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容