P8116 「Wdoi-1.5」魔理沙的计算器题目背景魔理沙是普通而平凡的魔法使。在解决了大大小小的异变后她终于攒足了足够多的钱在香霖堂里购置了一台Carno \verb!Carno!Carno计算器用来计算魔女之汤各种配料的含量之比。魔理沙早就听闻灵梦通过河童重工网络入手了一部Casio \verb!Casio!Casio计算器来计算神社的香火钱却买到了假货最多只能显示整数部分下取整。而魔理沙的这部可以精确到小数点后面若干位下取整的计算器。更高级的是这部计算器还可以支持其他的进制其强大的功能高出了灵梦一大截。因此作为灵梦真挚的朋友魔理沙希望向灵梦表达真挚的遗憾之情。正当魔理沙打算出发之时她发现虽然Carno \verb!Carno!Carno计算器不会导致一些特别大的误差但是在计算除法时仍然会出现一定的问题。考虑将计算器的进制调整为10 1010进制而计算器屏幕上最多可以显示5 55位数字小数点不计入显示位数。比如魔理沙希望计算1 ÷ 3 1\div 31÷3的值那么真正显示在屏幕上的则是0.3333 0.33330.3333按照道理上来讲1 ÷ ( 1 ÷ 3 ) 1\div(1\div 3)1÷(1÷3)结果应当等于3 33。但出乎意料的是当魔理沙输入1 ÷ 0.3333 1\div 0.33331÷0.3333后得到的结果却是3.0003 3.00033.0003这当然只是一个个例。当魔理沙计算1 ÷ ( 1 ÷ 4 ) 1\div(1\div 4)1÷(1÷4)时屏幕上显示出了正确的数字。为了防止在表达遗憾之情的时候自己的计算器也出了漏子魔理沙希望找到有多少个数字使得计算出的结果是正确的因此她向你求助了。题目描述魔理沙的计算器可以进行b bb进制的运算屏幕上可以显示k kk个数字不包含小数点。进行计算后若某个数字超出了屏幕就会被直接舍去例如b 10 b10b10时1 ÷ 7 0.142857 ⋯ 1\div 70.142857\cdots1÷70.142857⋯若屏幕大小为4 44那么最终显示为0.142 0.1420.142。魔理沙用计算器计算了1 ÷ n n ′ 1\div nn1÷nn′再计算1 ÷ n ′ n ′ ′ 1\div nn1÷n′n′′n ′ nn′和n ′ ′ nn′′均为显示在屏幕上的结果。魔理沙希望知道有多少个正整数n nn使得n n ′ ′ nnnn′′。你只需要输出这个答案对998 , 244 , 353 998,244,353998,244,353取模后的结果即可。输入格式第一行有一个正整数T TT表示数据组数。接下来T TT行每行有两个正整数b , k b,kb,k分别表示计算器的进制、屏幕上能显示的数字个数。输出格式输出共T TT行。每行输出一个整数。第i ii行的整数表示第i ii组数据中合法的n nn的总数对998 , 244 , 353 998,244,353998,244,353取模后的结果。输入输出样例 #1输入 #13 4 2 5 3 12 99输出 #13 3 19503说明/提示样例解释对于第一组询问符合条件的数转换成十进制为1 , 2 , 4 1,2,41,2,4。对于第二组询问符合条件的数转换成十进制为1 , 5 , 25 1,5,251,5,25。数据范围及约定subtask 分值 b ≤ k ≤ 特殊性质 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 \def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|c|}\hline \textbf{subtask}\textbf{分值} \bm{b\le} \bm {k\le } \textbf{特殊性质} \textbf{subtask 依赖} \cr\hline 1 20 10 7 - -\cr\hline 2 20 10^5 2 k2-\cr\hline 3 10 10^5 3 k3- \cr\hline 4 50 10^5 500 -1,2,3\cr\hline \end{array}subtask1234​分值20201050​b≤10105105105​k≤723500​特殊性质−k2k3−​subtask依赖−−−1,2,3​​对于100 % 100\%100%的数据满足1 ≤ T ≤ 10 1\le T\le 101≤T≤102 ≤ b ≤ 10 5 2\le b\le 10^52≤b≤1051 ≤ k ≤ 500 1\le k\le 5001≤k≤500。C实现#includebits/stdc.h#defineup(l,r,i)for(intil,END##ir;iEND##i;i)#definedn(r,l,i)for(intir,END##il;iEND##i;--i)usingnamespacestd;typedeflonglongi64;constintINF2147483647;constintMOD998244353;intqread(){intw1,c,ret;while((cgetchar())9||c0)w(c-?-1:1);retc-0;while((cgetchar())0c9)retret*10c-0;returnret*w;}intmain(){up(1,qread(),T){intbqread(),kqread(),ans1;if(k1){puts(1);continue;}for(inti2;i*ib;i){intc0;while(b%i0)c,b/i;ans1ll*ans*((k-1)*c1)%MOD;}if(b!1)ans1ll*ans*k%MOD;printf(%lld\n,ans);}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容