d188 - 11342 - Three-square
題目描述
題目要求判斷一個給定的正整數 K 是否能表示為三個非負完全平方數的和，如果可以，輸出字典序最小的解 (a, b, c)，其中 a <= b <= c。如果無法表示，則輸出 -1。
解題思路
題目限制 K 的範圍在 50000 以內，因此可以預先計算所有可能的平方數，並使用三重迴圈枚舉所有可能的組合。為了避免重複計算，可以設定迴圈的起始值，確保 a <= b <= c。預計算所有平方數可以減少運行時間。使用一個陣列 ans 儲存每個數字是否可以表示為三個平方數的和，以及對應的 a, b, c 值。
複雜度分析
- 時間複雜度: O(n^1.5)，其中 n 是 K 的最大值。預計算平方數的時間複雜度是 O(n)，三重迴圈的時間複雜度是 O(n^3)，但由於迴圈的起始值設定，實際迭代次數會減少。
- 空間複雜度: O(n)，用於儲存
ans陣列。
程式碼
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <stdio.h>
inline int read(){
int a(0);
char c('0');
while(c>='0'){
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a;
}
inline void write(int x) {
if(x==0)
putchar_unlocked('0');
else{
int stk[4],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
}
struct solution {
bool have = 0;
int a, b, c;
} ans[50001];
int dd[225];
int main(){
for(int i=0;i<225;++i)
dd[i]=i*i;
int sums,times,n;
for (int i = 0; i <= 130; ++i){
for (int j = i; j <= 159; ++j){
int ij=dd[i]+dd[j];
for (int k = j; k <= 224; ++k) {
sums = ij + dd[k];
if (sums > 50000)
break;
if (!ans[sums].have)
ans[sums].have = 1, ans[sums].a = i, ans[sums].b = j, ans[sums].c = k;
}
}
}
times=read();
while (times--) {
n=read();
if (ans[n].have){
write(ans[n].a);
putchar_unlocked(' ');
write(ans[n].b);
putchar_unlocked(' ');
write(ans[n].c);
putchar_unlocked('\n');
}
else{
putchar_unlocked('-');
putchar_unlocked('1');
putchar_unlocked('\n');
}
}
}