打卡信奥刷题（3304）用C++实现信奥题 P9118 [春季测试 2023] 幂次

P9118 [春季测试 2023] 幂次题目描述小 Ω 在小学数学课上学到了“幂次”的概念∀a,b∈N\forall a, b \in \N^∀a,b∈N定义aba^bab为bbb个aaa相乘。她很好奇有多少正整数可以被表示为上述aba^bab的形式由于所有正整数m∈Nm \in \N^m∈N总是可以被表示为m1m^1m1的形式因此她要求上述的表示中必须有b≥kb \geq kb≥k其中kkk是她事先选取好的一个正整数。因此她想知道在111到nnn中有多少正整数xxx可以被表示为xabx a^bxab的形式其中a,ba, ba,b都是正整数且b≥kb \geq kb≥k输入格式第一行包含两个正整数n,kn, kn,k意义如上所述。输出格式输出一行包含一个非负整数表示对应的答案。输入输出样例 #1输入 #199 1输出 #199输入输出样例 #2输入 #299 3输出 #27输入输出样例 #3输入 #399 2输出 #312说明/提示【样例 2 解释】以下是全部777组符合题意的正整数及对应的一种合法的表示方法。113,823,1624,2733,3225,6443,81341 1^3, 8 2^3, 16 2^4, 27 3^3, 32 2^5, 64 4^3, 81 3^4113,823,1624,2733,3225,6443,8134。注意某些正整数可能有多种合法的表示方法例如646464还可以表示为642664 2^66426。但根据题意同一个数的不同的合法表示方法只会被计入一次。【样例 3 解释】以下是全部121212组符合题意的正整数及对应的一种合法的表示方法。112,422,823,932,1642,2552,2733,3225,3662,4972,6482,81921 1^2, 4 2^2, 8 2^3, 9 3^2, 16 4^2, 25 5^2, 27 3^3, 32 2^5, 36 6^2, 49 7^2, 64 8^2, 81 9^2112,422,823,932,1642,2552,2733,3225,3662,4972,6482,8192。【样例 4】见选手目录下的 power/power4.in 与 power/power4.ans。【样例 5】见选手目录下的 power/power5.in 与 power/power5.ans。【样例 6】见选手目录下的 power/power6.in 与 power/power6.ans。【数据范围】对于所有数据保证1≤n≤10181 \leq n \leq 10^{18}1≤n≤10181≤k≤1001 \leq k \leq 1001≤k≤100。测试点编号n≤n \len≤kkk110210^2102111210210^2102≥2\ge 2≥2310410^4104≥3\ge 3≥3410410^4104≥2\ge 2≥2510610^6106≥3\ge 3≥3610610^6106≥2\ge 2≥2710810^8108≥3\ge 3≥3810810^8108≥2\ge 2≥29101010^{10}1010≥3\ge 3≥310101010^{10}1010≥2\ge 2≥211101210^{12}1012≥3\ge 3≥312101210^{12}1012≥2\ge 2≥213101410^{14}1014≥3\ge 3≥314101410^{14}1014≥2\ge 2≥215101610^{16}1016≥3\ge 3≥316101610^{16}1016≥2\ge 2≥217101810^{18}1018≥3\ge 3≥318101810^{18}1018≥2\ge 2≥219101810^{18}1018≥2\ge 2≥220101810^{18}1018≥2\ge 2≥2C实现#includebits/stdc.husingnamespacestd;#definelllonglongmapll,boolmp;ll x,cnt;voidsolve(ll n,ll k){for(ll i2;i*i*in;i){ll ti*i,m2;while(tn/i){t*i,m;if(mk)continue;if(mp[t])continue;if((ll)sqrtl(t)*sqrtl(t)t)x;mp[t]1,cnt;}}}intmain(){ll n,k;cinnk;solve(n,k);if(k1)coutn;elseif(k3)coutcnt1;elsecout(ll)sqrtl(n)cnt-x;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容