洛谷P1586 四方定理

P1586 四方定理

题目描述

四方定理是众所周知的：任意一个正整数 $n$ ，可以分解为不超过四个整数的平方和。例如： $25=1^{2}+2^{2}+2^{2}+4^{2}$ ，当然还有其他的分解方案， $25=4^{2}+3^{2}$ 和 $25=5^{2}$ 。给定的正整数 $n$ ，编程统计它能分解的方案总数。注意： $25=4^{2}+3^{2}$ 和 $25=3^{2}+4^{2}$ 视为一种方案。

输入输出格式

输入格式：

第一行为正整数 $t$ ( $t\le 100$ )，接下来 $t$ 行，每行一个正整数 $n$ ( $n\le 32768$ )。

输出格式：

对于每个正整数 $n$ ，输出方案总数。

输入输出样例

输入样例#1：

1
2003

输出样例#1：

两种做法，暴力枚举或DP。
这里着重说DP。因为暴力枚举轻易被卡掉

【状态】
dp[i][j]表示i用j个数的平方表示的方案数
【转移方程】
dp[i][j] = Σdp[i - k * k][j - 1]
【初始状态】
dp[0][0] = 1
【结果】
dp[n][1] + dp[n][2] + dp[n][3] + dp[n][4]
【注意事项】

如果按照i->j->k的顺序转移，当i - k * k也是完全平方数时，方案会算重。如计算dp[5][2]时，会累加dp[4][1]和dp[1][1]，但其实二者的本质是相同的。
因此，我们要按照k->i->j的顺序转移，k从小到大递增，保证了方案的唯一性

Code DP

 1 #include <bits/stdc++.h>
 2 
 3 inline void read(long long &x)
 4 {
 5     x = 0;char ch = getchar();char c = ch;
 6     while(ch > '9' || ch < '0')c = ch, ch = getchar();
 7     while(ch <= '9' && ch >= '0')x = x * 10 + ch - '0', ch = getchar();
 8     if(c == '-')x = -x;
 9 }
10 const int INF = 0x3f3f3f3f;
11 
12 //dp[i][j]表示i用j个平方数表示的方案数
13 //转移：dp[i][j] = dp[i - k * k][j - 1]
14 //
15 
16 long long t,n,dp[(1 << 15) + 10][5];
17 long long ans;
18  
19 int main()
20 {
21     read(t);
22     dp[0][0] = 1;
23     for(int i = 1;i <= (1 << 14);++ i)
24         for(int j = i * i;j <= (1 << 15);++ j)
25             for(int k = 1;k <= 4;++ k)
26                 dp[j][k] += dp[j - i * i][k - 1];
27     for(;t;--t)
28     {
29         read(n);
30         printf("%d
", dp[n][1] + dp[n][2] + dp[n][3] + dp[n][4]);
31     }
32     return 0;
33 }

View Cod

Code 暴力

 1 #include <bits/stdc++.h>
 2 
 3 inline void read(long long &x)
 4 {
 5     x = 0;char ch = getchar();char c = ch;
 6     while(ch > '9' || ch < '0')c = ch, ch = getchar();
 7     while(ch <= '9' && ch >= '0')x = x * 10 + ch - '0', ch = getchar();
 8     if(c == '-')x = -x;
 9 }
10 const int INF = 0x3f3f3f3f;
11 const int MAXN = 1 << 15;
12 
13 long long t,n,dp[MAXN + 10][5];
14 long long ans;
15  
16 int main()
17 {
18     read(t);
19     for(;t;--t)
20     {
21         ans = 0;
22         read(n);
23         for(int i = 0;i * i <= n;i ++)
24         {
25             int tmp1 = i * i;
26             for(int j = i;tmp1 + j * j <= n;j ++)
27             {
28                 int tmp2 = tmp1 + j * j;
29                 for(int k = j;tmp2 + k * k <= n;k ++)
30                 {
31                     int tmp3 = tmp2 + k * k;
32                     int c = n - tmp3;
33                     if(c < k * k)break;
34                     int m = sqrt(c);
35                     if(m * m == c)ans ++;
36                 }
37             }
38         }
39         printf("%lld
", ans);
40     }
41     return 0;
42 }

View Code