題目要求

P1679題目鏈接

分析

可以使用DP去做，當做“完全背包問題”問題來處理。

初值：$f[0]=0$

$cost[]$ ： $cost[i]=i?i?i?i$

狀態轉移方程：$f[j]=Math.min(f[j],f[j?cost[i]]+1)$

AC代碼（Java語言描述）

import java.util.Arrays; import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int num = scanner.nextInt();scanner.close();int[] f = new int[num+1];Arrays.fill(f, (int)1e8);f[0] = 0;int limit = (int)Math.pow(num, 0.25);int[] cost = new int[limit+1];for (int i = 0; i <= limit; i++) {cost[i] = i*i*i*i;}for(int i = 1; i <= limit; i++) {for(int j = cost[i]; j <= num; j++) {f[j] = Math.min(f[j], f[j-cost[i]]+1);}}System.out.println(f[num]);} }

拓展

如果把四次方數改為平方數，就可以依據“拉格朗日四平方和定理”來求解。

拉格朗日四平方和定理

強勢安利“$拉格朗日四平方和定理$”：每個正整數均可表示為 $4$ 個整數的平方和。

定理內容
每個正整數均可表示成 $4$ 個整數的平方之和。

定理說明
注意有些整數不可表示為 $3$ 個整數的平方和，例如 $7$。

重要的推論

數 n 如果只能表示成四個整數的平方和，不能表示成更少的數的平方之和，必定滿足 $4a(8b+7)$。

如果 $n$，$k=\frac{n}{4}$，$n$ 和 $k$ 可由相同個數的整數表示。

定理證明
$from$ 知乎

如何利用推論求一個正整數最少需要多少個數的平方和表示

先判斷這個數是否滿足 $4a(8b+7)$，如果滿足，那么這個數就至少需要 $4$ 個數的平方和表示。

如果不滿足，再在上面除以 $4$ 之后的結果上暴力嘗試只需要 $1$ 個數就能表示和只需要 $2$ 個數就能表示的情況。

如果還不滿足，那么就只需要 $3$ 個數就能表示。

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的神奇的四次方数（洛谷P1679题题解，Java语言描述）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。