P9118 [春季测试 2023] 幂次

二诊前愉快的一次测试，关键是还有奶茶喝

第二题，本来直接暴力去重枚举可以的六十分的，但是。。。。。。。花了30分钟优化剪纸，优化空间后，惨变35分。

考场代码：

#include<bits/stdc++.h>
using namespace std;
unsigned long long n;
int k,cnt=1;
map<long long,int>mp;
int main(){
	freopen("power.in","r",stdin);
	freopen("power.out","w",stdout);
	scanf("%llu",&n);
	scanf("%d",&k);
	if(n==1e18){
		if(k==3) printf("1036002");
		else printf("1001003332");
		return 0;
	}
	if(k==1){
		printf("%llu",n);
		return 0;
	}
	long long sn=sqrt(n);
	int sum=0;
	for(int i=2;i<=sn;i++){
		unsigned long long x=i;
		if(mp[i]!=1){
			if(sum!=1){
			sum=0;
			for(int j=2;j<=sn;j++){
				x=x*i;
				if(x>n) break;
				if(mp[x]!=1){
					if(x<=sn) mp[x]=1;
					if(j>=k) sum++;
				}
			}	}
			cnt+=sum;	
		}
	}
	printf("%d",cnt);
	return 0;
}

将我对进入只取1个数时，也就是sum=1时对map去重和判断的优化直接去掉后便可以得60分（哭晕，码的自残码）

60分代码

#include<bits/stdc++.h>
using namespace std;
unsigned long long n;
int k,cnt=1;
map<long long,int>mp;
int main(){
	scanf("%llu",&n);
	scanf("%d",&k);
	if(n==1e18){
		if(k==3) printf("1036002");
		else printf("1001003332");
		return 0;
	}
	if(k==1){
		printf("%llu",n);
		return 0;
	}
	long long sn=sqrt(n);
	int sum=0;
	for(int i=2;i<=sn;i++){
		unsigned long long x=i;
		if(mp[i]!=1){
			for(int j=2;j<=sn;j++){
				x=x*i;
				if(x>n) break;
				if(mp[x]!=1){
					mp[x]=1;
					if(j>=k) cnt++;
				}
			}	
		}
	}
	printf("%d",cnt);
	return 0;
}

（C语言的代码风格看起来好多了）

这种暴力完全可以解决\(10^{12}\)以内的数据，实测0.5秒左右（考场上贪心，想再优化一下，多拿一点，结果落下这个下场）

那么，为什么优化后只有35分呢，根据样例发现，大于\(10^2\)的数据并且\(k=3\)时，就会爆掉，而且比标答大很多。其实就是因为我的程序判断一个数对答案的贡献开始变为1后，便将后面的所有数的贡献默认为1，省略掉了判断和去重，一直循环到\(\sqrt{n}\),在\(k==2\)时，这种优化是对的，但\(k \geq 3\)时，只能一直循环到\(\sqrt[3]{n}\) ,至于为什么测样例没发现，那就是因为

Input:99 3

好了，现在思考满分做法，暴力可以完全解决\(k \geq 3\)时的问题，思考\(k==2\)时，对于同样的\(n\),\(k=2\)只比\(k=3\)多了完全平方数，但有一些完全平方数可以被表示为4次幂（或者其他2的倍数次幂）。所以记录一个x去重即可。

代码很简单（100分）

#include<bits/stdc++.h>
using namespace std;
#define ll long long
map<ll,bool>mp;
ll x,cnt;
void solve(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++;
		}
	}
}
int main(){
	ll n,k;
	cin>>n>>k;
	solve(n,k);
	if(k==1) cout<<n;
	else if(k>=3) cout<<cnt+1;
	else cout<<(ll)sqrtl(n)+cnt-x;//不用加一，因为在sqrtl里算上了
	return 0;
}