这里提供一个非常暴力但是期望复杂度很低的算法。
不难想到要么就是全部放 \(1\),要么就是取出一个最大的质数,然后对于剩下的部分继续按照这样的策略求答案。
因为质数间隔不大,然后暴力判断质数复杂度是 \(O(\sqrt n)\) 的,再加上 IOI 的 buff,我们可以直接考虑从大到小枚举质数,因为取到最后取的次数也不多,预期复杂度就是 \(O(\sqrt n)\) 乘上一个比较大的常数,实际情况跑的很快。
\(Code\)
bool check(int x){//暴力判断质数(1也算)
if(x<=2)return 1;
if(x+1&1)return 0;
for(int j=3;j*j<=x;j+=2)if(x%j==0)return 0;
return 1;
}
ll work(int n,int k,int i=0){//暴力递归求解
if(!n)return 0;
for(i=n;!check(i);--i);
if(1ll*(i-k)*(i-k)<=1ll*i*(k-1)*(k-1))return 1ll*n*(k-1)*(k-1);
return work(n-i,k)+1ll*(i-k)*(i-k);
}
int main(){
for(int T=read();T--;){
int n=read(),k=read();
printf("%lld\n",work(n,k));
}
return 0;
}
标签:暴力,题解,质数,sqrt,P9817,复杂度
From: https://www.cnblogs.com/NBest/p/17808553.html