P9118 [春季测试 2023] 幂次
题目描述
小 Ω 在小学数学课上学到了“幂次”的概念：∀a,b∈N+\forall a, b \in \N^+∀a,b∈N+，定义aba^bab为bbb个aaa相乘。
她很好奇有多少正整数可以被表示为上述aba^bab的形式？由于所有正整数m∈N+m \in \N^+m∈N+总是可以被表示为m1m^1m1的形式，因此她要求上述的表示中，必须有b≥kb \geq kb≥k，其中kkk是她事先选取好的一个正整数。
因此她想知道在111到nnn中，有多少正整数xxx可以被表示为x=abx = a^bx=ab的形式，其中a,ba, ba,b都是正整数，且b≥kb \geq kb≥k？
输入格式
第一行包含两个正整数n,kn, kn,k，意义如上所述。
输出格式
输出一行包含一个非负整数表示对应的答案。
输入输出样例 #1
输入 #1
99 1输出 #1
99输入输出样例 #2
输入 #2
99 3输出 #2
7输入输出样例 #3
输入 #3
99 2输出 #3
12说明/提示
【样例 2 解释】
以下是全部777组符合题意的正整数及对应的一种合法的表示方法。
1=13,8=23,16=24,27=33,32=25,64=43,81=341 = 1^3, 8 = 2^3, 16 = 2^4, 27 = 3^3, 32 = 2^5, 64 = 4^3, 81 = 3^41=13,8=23,16=24,27=33,32=25,64=43,81=34。
注意某些正整数可能有多种合法的表示方法，例如646464还可以表示为64=2664 = 2^664=26。
但根据题意，同一个数的不同的合法表示方法只会被计入一次。
【样例 3 解释】
以下是全部121212组符合题意的正整数及对应的一种合法的表示方法。
1=12,4=22,8=23,9=32,16=42,25=52,27=33,32=25,36=62,49=72,64=82,81=921 = 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^21=12,4=22,8=23,9=32,16=42,25=52,27=33,32=25,36=62,49=72,64=82,81=92。
【样例 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≤1018，1≤k≤1001 \leq k \leq 1001≤k≤100。
| 测试点编号 | n≤n \len≤ | kkk |
|---|---|---|
| 1 | 10210^2102 | =1=1=1 |
| 2 | 10210^2102 | ≥2\ge 2≥2 |
| 3 | 10410^4104 | ≥3\ge 3≥3 |
| 4 | 10410^4104 | ≥2\ge 2≥2 |
| 5 | 10610^6106 | ≥3\ge 3≥3 |
| 6 | 10610^6106 | ≥2\ge 2≥2 |
| 7 | 10810^8108 | ≥3\ge 3≥3 |
| 8 | 10810^8108 | ≥2\ge 2≥2 |
| 9 | 101010^{10}1010 | ≥3\ge 3≥3 |
| 10 | 101010^{10}1010 | ≥2\ge 2≥2 |
| 11 | 101210^{12}1012 | ≥3\ge 3≥3 |
| 12 | 101210^{12}1012 | ≥2\ge 2≥2 |
| 13 | 101410^{14}1014 | ≥3\ge 3≥3 |
| 14 | 101410^{14}1014 | ≥2\ge 2≥2 |
| 15 | 101610^{16}1016 | ≥3\ge 3≥3 |
| 16 | 101610^{16}1016 | ≥2\ge 2≥2 |
| 17 | 101810^{18}1018 | ≥3\ge 3≥3 |
| 18 | 101810^{18}1018 | ≥2\ge 2≥2 |
| 19 | 101810^{18}1018 | ≥2\ge 2≥2 |
| 20 | 101810^{18}1018 | ≥2\ge 2≥2 |
C++实现
#include<bits/stdc++.h>usingnamespacestd;#definelllonglongmap<ll,bool>mp;ll x,cnt;voidsolve(ll n,ll k){for(ll i=2;i*i*i<=n;i++){ll t=i*i,m=2;while(t<=n/i){t*=i,m++;if(m<k)continue;if(mp[t])continue;if((ll)sqrtl(t)*sqrtl(t)==t)x++;mp[t]=1,cnt++;}}}intmain(){ll n,k;cin>>n>>k;solve(n,k);if(k==1)cout<<n;elseif(k>=3)cout<<cnt+1;elsecout<<(ll)sqrtl(n)+cnt-x;return0;}后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
