春测2023 T2题解

这是一个从暴力到正解的过程。

暴力

从 \(1\) 枚举到 \(\sqrt n\)，枚举每一个 \(x\)，进行累乘，顺便用一个map数组判重，时间复杂度\(\mathcal{O}(\sqrt n\log n\log n)\)，直接T飞。

改善1

此时我们抛开复杂度的 \(\log n\log n\) 不谈，发现当枚举的 \(i\) 大于 \(n^{\frac{1}{3}}\) 小于等于 \(\sqrt n\) 时，只能够算它的方，没有必要枚举。

故如果 \(k=2\)，我们在枚举时，如果当前指数为 \(b\)，则当 \(b\) 为双数时（因为就是 \((a^{\frac{b}{2}})^2\)，同样也是某数的方），故意不加答案，等最后令答案加上 \(\sqrt n\) 就行，这样复杂度降至 \(\mathcal{O}(n^{\frac{1}{3}}\log n\log n)\)。

改善2

试着不用map数组判重，假设 \(b>d,a^b=c^d\)，则必有 \(a^e=c\)，所以我们在枚举时，当 \(a^b\leq10^6\) 时，\(vis[a^b]=1\)。

这样在枚举底数时，如果自己已经被算过，直接下一个，既不会有重复，又优化了复杂度。复杂度 \(\mathcal{O}(n^{\frac{1}{3}}\log n)\)，可过此题。

上代码

#include<bits/stdc++.h>
#define int __int128
using namespace std;
bool vis[2000000];

int ll=0; 
inline __int128 read(){
    __int128 x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
inline void print(__int128 x){
    if(x<0){putchar('-');x=-x;}
    if(x>9)print(x/10);
    putchar(x%10+'0');
}
signed main(){
//	freopen("power.in","r",stdin);
//	freopen("power.out","w",stdout);
	long long n,k;
	cin>>n>>k;
	if(k==1){
		print(n);return 0;
	}
	if(k>log2(n)){
		cout<<1;return 0;
	}
	int ans=1;
	int b=0;
	for(int a=2;a<=1000000;a++){
		int res=a;b=1;
		if(vis[res])continue;
		while(1){
			b++;
			res=res*a;
			if(b>=k&&res<=n){
				if(k==2&&res<=n&&b%2==0){//只有k=2时才需要进行优化二 
					if(res<=1000000)vis[res]=1;//标记 
					continue;//不加答案 
				}
				ans++;
			}
			if(res<=1000000)vis[res]=1;//注意不管符不符合答案就会标记上 
			if(res>=n)break;
		}
	}
	if(k==2)ans+=(int)sqrtl(n)-1;//因为ans初值为1，表示1也符合答案，所以在这里sqrtl(n)也包含了1，需减去 
	print(ans);
	return 0;
}