这题感觉是有意思的。
先考虑构造 \(m\) 个 \(p_i\)，答案为 \(m\times (1-k)^2\)。
然后考虑什么情况下是更优的。尽可能使 \((p_i-k)^2\) 大，那就要尽可能与 \(k\) 的差值大，当 \(p_i\leq k\) 时肯定是全为 \(1\) 最优。那么如果我们要写出一个 \(p_i>k\)，我们对答案的更改是 \((p_i-k)^2-p_i\times (1-k)^2\)，就相当于是删掉了 \(p_i\) 个 \(1\)，添加了一个 \(p_i\)。所以只有当 \((p_i-k)^2>p_i\times (1-k)^2\) 我们才有必要写上 \(p_i\)。再说对于两个均满足条件的 \(p_i,p_j(p_i<p_j)\) 我们一定是贪心的先添加 \(p_j\) 更优。
所以，我们设 \(f(x)\) 为 \(n=x\) 时最大的答案，\(p_i\) 为最大的小于等于 \(x\) 的质数，则
\[f(x)=\begin{cases} f(x-p_i)+(p_i-k)^2 & (p_i-k)^2>p_i\times (1-k)^2\\ x\times (1-k)^2 & (p_i-k)^2\leq p_i\times (1-k)^2\end{cases} \]我们直接暴力递归进行，暴力找到当前 \(p_i\)。要有优化，即若当前 \((p_i-k)^2\leq p_i\times (1-k)^2\) 我们直接结束（\(p_i\) 越大越有可能满足条件），返回 \(x\times (1-k)^2\)。同时判断是否是质数时若找到了一个因子就直接跳出。
因为 \(x-p_i\) 不会很大，所以暴力找 \(p_i\) 的复杂度是正确的，递归因此也不会很多次，所以时间复杂度为 \(O(\text{良好})\)。
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#define int long long
using namespace std;
int T,n,k;
int DO(int x)
{
if(2*k<=x)
{
for(int tmp=x;2*k<=tmp&&(tmp-k)*(tmp-k)>tmp*(k-1)*(k-1);--tmp)
{
bool flag=false;
for(int i=2;i<=sqrt(tmp);++i)
if(!(tmp%i)){flag=true;break;}
if(!flag) return (tmp-k)*(tmp-k)+DO(x-tmp);
}
}
return x*(k-1)*(k-1);
}
main()
{
#ifdef ONLINE_JUDGE
cin.tie(0),cout.tie(0);
ios::sync_with_stdio(0);
#endif
cin>>T;
while(T--)
{
cin>>n>>k;
cout<<DO(n)<<'\n';
}
}