首先众所周知这道题目要用 DP 做。
还是比较好好想的：
- 定义状态： dp[i] 表示正整数 i 最少需要几个完全平方数所相加。
- 初始化：因为一个数 n 最多要用 n 个 1^2 表示，所以将 dp[i] 初始化为 i 。
- 状态转移方程： 对于每个 i(1≤i≤n) ，和每个 j(1≤j^2≤i) 都有 dp[i]=min(dp[i],dp[i-j^2]+1) 。
好了，这个三要素有了代码就简单了，放个核心代码：
for(int i=1;i<=n;i++)for(int j=1;j*j<=i;j++)dp[i]=min(dp[i],dp[i-j*j]+1);
对，不要惊讶，这道题目很简单，核心 DP 部分只要一行，其他就都是输入输出了。
好了，这篇题解还没有完，因为还有数学的一些拓展：
- 四平方和定理（拉格朗日四平方和定理）
- 对于任意正整数 n ，都可以表示为不超过四个正整数的平方和，即 n=a^2+b^2+c^2+d^2 ，其中 a,b,c,d∈N 。
- 一种特殊情况： n=4^{a}(8b+7)
- 根据数论知识可知正整数 n 不能被三个完全平方数和表示的充要条件是 n=4^{a}(8b+7) 其中 a,b∈N 。对于这样的数，我们最少需要用 4 个数来表示
- 勒让德三平方和定理
- 一个正整数 n 能表示为三个整数的平方和 n=a^2+b^2+c^2 ，当且仅当 n\not\equiv 7 (\mathrm{mod}\ 8) 且 n\not\equiv 4^{k}(8m+7),\ k,m∈N 。这意味着如果一个数不满足 n=4^k(8m+7) 这种形式，那么它就可以用三个完全平方数的和来表示。
- 费马平方和定理
- 奇质数能表示为两个平方数之和 p=x^2+y^2, \ x,y∈Z 的充要条件是 p\equiv 1(\mathrm{mod} \ 4) 。也就是说，当奇质数除以 4 的余数为 1 时，它可以表示为两个完全平方数之和，反之也成立。
- 对于一般的正整数 n ，能表示为两个完全平方数之和的充分必要条件是： n 的所有形如 4k+3, \ k∈Z 的质因数的幂次都是偶数。
- 证明的思路：
- 必要性：假设 p 是一个能表示为两个平方数之和的奇质数，即 p=x^2+y^2 。通过对 x 、 y 的奇偶性分析以及模运算的性质，可以推出。
- 充分性：对于的奇质数 p ，利用数论中的一些工具，如二次剩余理论、高斯整数环的性质等，可以构造出满足 p=x^2+y^2 的整数 x 和 y 。对于一般正整数 n ，根据其质因数分解以及唯一分解定理，结合奇质数的情况来证明其能表示为两个完全平方数之和的条件。
- 那么如果一个数最少被一个完全平方数表示的条件是什么？当然是这个数自己是完全平方数啦，一定要说出充要条件的话就是对于一个数 n∈N 它的算术平方根为整数时成立，即 \sqrt{n} ∈ Z ，想用 C++ 完成判断可以用 Miller_rabin 素性检测来实现。
根据我的习惯讲到判断素数就必须要将！
- 首先我们有第一种方法试除法：
这肯定就是枚举啦，但是我们可以优化哦！
比如当你枚举到 \sqrt n 的时候你会发现后面在枚举就会出现重复所以我们枚举到 \sqrt n 就行了！时间复杂度为 O(\sqrt n) 好了这个太简单了，放个代码：
#include<bits/stdc++.h>
#define I using
#define AK namespace
#define IOI std
#define i_ak return
#define ioi 0
I AK IOI;
int n;
int main(){
//freopen("","r",stdin);
//freopen("","w",stdout);
cin>>n;
for(int i=2;i*i<=n;i++){
if(n%i==0){
puts("no");
return 0;
}
}
puts("yes");
i_ak ioi;
}
- 然后就是埃式筛与欧拉筛：
其实这两种筛法都围绕了同一个思想就是： 素数的倍数不是素数。
埃式筛的思想就是给出从 2 到 n 的所有数，并且从 2 开始将 2 的倍数并且不大于 n 的数全部去掉，以此类推，直到到 \sqrt n 结束。没有被去掉的数，就是素数。
这种筛法的时间复杂度为： O(n\log \log n)
放个模板代码：
#include<bits/stdc++.h>
#define I using
#define AK namespace
#define IOI std
#define i_ak return
#define ioi 0
I AK IOI;
int n,i,j,flag,a[100005];
int main(){
cin>>n;
for(i=2;i<=n/i;i++)if(a[i]==0)for(j=2;i*j<=n;j++)a[i*j]=1;
for(i=2;i<=n;i++){
if(a[i]==0){
flag=1;
cout<<i<<endl;
}
}
i_ak ioi;
}
而欧拉筛的时间复杂度为 O(n) 。
然后我们放一个欧拉筛的模板代码：
#include<bits/stdc++.h>
#include<bitset>//需要引入头文件
#define I using
#define AK namespace
#define IOI std
#define i_ak return
#define ioi 0
I AK IOI;
bitset<1000001>a;//定义方式，这里就相当于定义bool a[1000001];
int b[100001];//存质数
long long n,cnt;
int main(){
cin>>n;
for (int i=2;i<=n;i++){
if(!a[i])b[++cnt]=i;
for(int j=1;j<=cnt;j++){
if(i*b[j]>n)break;//如果超出给出的范围，那么就退出循环
a[i*b[j]]=1;//素数的倍数不是素数，进行标记。
if(i%b[j]==0)break;//超级关键的只标记一次
}
}
for(int i=1;i<=cnt;i++)cout<<b[i]<<' ';
}
注意这里我们使用了 bitset 是因为当 n 的范围过大时，其他像 vector 占用的内存会很高，而这里的 bitset 和 bool 类型差不多也是每一个位置存储 0 或 1 并且它每一个位置只需要占用 1\ \ bit 的空间十分划算。
记下来我们来讨论一个问题：为什么欧拉筛更快？
因为埃式筛它会重复标记一个数，比如： 6 它在 2 被标记过一次，在 3 也标记过一次这样就会浪费很多时间，那欧拉筛呢？
我们注意到 if(i%b[j]==0)break; 这一个判断让我们不会重复计算同一个数，这样就不会浪费时间了！
- 接下来我们来讲 Miller_rabin 素性检测！
算法原理我们是依据了费马小定理：若 p 为质数，则 a^{p-1}\equiv 1 (\mathrm{mod} \ p) 但是我们是知道费马小定理的逆命题是不成立的，比如：卡迈克尔数。
但是我们可以把这个错误率降到最小，算法还是很好的。
接着我们还需要知道二次探测定理：
若 p∈\mathbb{P} ,a^2 \equiv 1(\mathrm{mod} \ P) 那么 a\equiv ± 1(\mathrm{mod} \ P) 。
有定理不能不证明！
首先我们移项得到： \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ a^2-1 \equiv 0(\mathrm{mod} \ P)\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (a+1)\times(a-1)\equiv 0(\mathrm{mod} \ P)
那么我们有要么是 (a+1)\equiv 0(\mathrm{mod} \ P) 要么是 (a-1)\equiv 0(\mathrm{mod} \ P)
即 a \equiv ±1(\mathrm{mod} \ P)
现在证明完毕了，我们假设要判断的素数为 p 那么将 p-1 分解为 2^k\times t 的形式。
那么当 p 为素数时，有 a^{2^k\times t}\equiv 1(mod \ p)
我们随机选择一个数 n 算出 a^t (\mathrm{mod} \ p) 的值，让其不断地自乘，结合二次探测定理进行判断，如果我们乘出来的数模 p 余 1 ，但是我们之前的数并不符合，那么这个数就是合数。
这样一直乘 k 次，最后得到的数就是 a^{p-1} 。
那么如果最后计算出来的数不是 1 那么这个数也是合数！
那么算法复杂度是多少呢？非常乐观只有 O(k \log n) 其中 k 未检测次数。
放上模板代码（只放函数部分）：
int primes[19]={2,3,5,7,11,13,17,19,23,29,31,37};
ll poww(ll a,ll b,ll c){
ll ans=1;__int128 base=a;
while(b){
if(b&1)ans=ans*base%c;
base=base*base%c;
b>>=1;
}
return ans;
}
bool miller_rabin(ll n){
for(int i=0;i<=8;i++){
if(primes[i]==n)return 1;
else if(primes[i]>n)return 0;
ll t=poww(primes[i],n-1,n),x=n-1;
if(t!=1)return 0;
while(t==1&&x%2==0){
x/=2;
t=poww(primes[i],x,n);
if(t!=1&&t!=n-1)return 0;
}
}
return 1;
}
那么由 Miller_rabin 算法衍生的算法还有很多，比如说要用到素数判断的 pfc 和 Pollard_rho 。
好了题解就到这里了，我们讲解了 DP 思路和数学拓展，希望对您有帮助哦~
打字不易，留下您的一些小心意吧~