简要题意
有 \(1\le T\le 10^6\) 次询问，每次询问正整数 \(x,p\)，\(p\) 为素数，令 \(n=xp^2\)，问是否存在三个正整数 \(a,b,c\)，满足 \(ab+bc+ca=n\)。有的话给出构造，否则输出 \(-1\) 。
solution
打表注意到只有 \(n=4,18\) 是无解的。
打表
namespace DB
{
const int N=1e5;
struct node{int x,y,z;}db[N+5];
inline void init()
{
for(int i=1;i<=N;i++)
{
bool ok=1;
for(int a=1;a*a<=i;a++)
{
for(int b=1;b*b<=i;b++)
{
int t=i-a*b;if(t<=0) continue;
if(t%(a+b)==0){db[i]={a,b,t/(a+b)};ok=0;break;}
}
if(!ok) break;
}
}
}
}using DB::db;
这里尽管理论复杂度是 \(O(N^2)\) 的，但是实际跑 \(10^5\) 大约 \(0.2s\) 不到。我大概跑了 \(N=10^6\) 验证只有那两个无解。
下面做法不依赖与 \(n=xp^2\)
考虑钦定其中一个数 \(c\) 为 \(r\)，两边同时
标签：10,le,int,Day5,T3,打表,xp,省队 From： https://www.cnblogs.com/HaHeHyt/p/17548636.html