例36 四方定理
题目描述
四方定理是众所周知的:任意一个正整数n,可以分解为不超过四个整数的平方和。例如:25=12+22+22+42,当然还有其他的分解方案,25=42+32和25=52。给定的正整数n,编程统计它能分解的方案总数。注意:25=42+32和25=32+42视为一种方案。
输入格式
第一行为正整数t(t≤100),接下来t行,每行一个正整数n(n≤32768)。
输出格式
对于每个正整数n,输出方案总数。
输入样例
1
2003
输出样例
48
(1)编程思路1。
设n=a2+b2+c2+d2,用4重循环对a、b、c、d的取值组合进行穷举。其中
0≤a≤sqrt(n) , a≤b≤sqrt(n) , b≤c≤sqrt(n) , c≤d≤sqrt(n)
(2)源程序1。
#include <stdio.h>
#include <math.h>
int main()
{
int t;
scanf("%d",&t);
while (t--)
{
int n;
scanf("%d",&n);
int cnt=0;
int a,b,c,d;
for (a=0;a<sqrt(n);a++)
for (b=a;b<sqrt(n);b++)
for (c=b;c<sqrt(n);c++)
for (d=c;d<=sqrt(n);d++)
{
if (a*a+b*b+c*c+d*d==n) cnt++;
}
printf("%d\n",cnt);
}
return 0;
}
(3)编程思路2。
若a,b,c的取值确定后,d可以通过sqrt(n-a*a-b*b-c*c)确定,因此,可以将上面的4重穷举循环改写成3重循环。
(4)源程序2。
#include <stdio.h>
#include <math.h>
int main()
{
int t;
scanf("%d",&t);
while (t--)
{
int n;
scanf("%d",&n);
int cnt=0;
int a,b,c,d;
for (a=0; a<sqrt(n); a++)
for (b=a; b<sqrt(n); b++)
for (c=b; c<sqrt(n); c++)
{
if (a*a+b*b+c*c>=n)
break;
d=sqrt(n-a*a-b*b-c*c);
if (d<c)
break;
if (a*a+b*b+c*c+d*d==n)
cnt++;
}
printf("%d\n",cnt);
}
return 0;
}
(5)编程思路3。
由于题目中n的最大值为32768。因此,可以定义一个数组hash[32769],其中,hash[i]的值为正整数i分解为4个数的平方和的方案数。初始时,置所有的元素值均为0,表示方案数为0。再用4重循环对a、b、c、d进行穷举,若a*a+b*b+c*c+d*d没有超出32768的范围,则对应的hash[a*a+b*b+c*c+d*d]加1,从而求出1~32768中各整数的可分解方案数。这样,对于每个输入的n,直接输出hash[n]的值即可。
(6)源程序3。
#include <stdio.h>
#include <math.h>
int main()
{
int t,n;
scanf("%d",&t);
int hash[32769]={0};
int a,b,c,d;
n=32768;
for (a=0; a<=sqrt(n/4); a++)
for (b=a; b<=sqrt(n/3); b++)
for (c=b; c<=sqrt(n/2); c++)
for (d=c;d<=sqrt(n);d++)
{
if (a*a+b*b+c*c+d*d>n)
break;
hash[a*a+b*b+c*c+d*d]++;
}
while (t--)
{
scanf("%d",&n);
printf("%d\n",hash[n]);
}
return 0;
}
习题36
36-1 拼木棒
本题选自洛谷题库 (https://www.luogu.org/problem/P3799)
题目描述
有 n 根木棒,现在从中选 4 根,想要组成一个正三角形,问有几种选法?
答案对109+7 取模。
输入格式
第一行一个整数 n(1≤n≤5×105)。
第二行 n 个整数,第 i 个整数 ai (0≤ai≤5×103)代表第 i 根木棒的长度。
输出格式
一行一个整数代表答案。
输入样例
4
1 1 2 2
输出样例
1
(1)编程思路。
设所取的四个木棒长度分别为 a,b,c,d,不妨设a≤b≤c≤d。要用所取的4根木棒组成一个正三角形,则必有2根长度相等,且另外2根长度之和,等于前2根相等的木棒的长度。即只有四个木棒的长度分别为 a,b,a+b(=c)和 a+b(=d)的时候才能拼成一个正三角形。
可直接用两层循环,枚举a和b两种木棒的长度,计算方案数并累加。
设所有木棒中最短的木棒长度为min,最长木棒的长度为max。则枚举范围可确定为:
min≤a≤max/2 a≤b≤max-min
枚举时,考虑两种情况
①当 a≠b时,可取组合的数量=长度为a 的木棒数量×长度为b的木棒数量×长度为 (a+b) 的木棒任取2根的组合数。
②当 a=b时,由于这里已经取走了一根长度为a的木棒,那么再取一根长度为 a的木棒的方案数就要减1。可取组合的数量=长度为a 的木棒任取2根的组合数×长度为 (a+b)的木棒任取2根的组合数。
将所有的可取数量累加起来即可得到答案。
为了处理方便,在输入时预处理。定义数组int t[5001];其中元素t[i]保存长度为i的木棒的个数。初始值全为0。
(2)源程序。
#include <stdio.h>
#define MOD 1000000007
long long C2(long long x)
{
return (x*(x-1)/2)%MOD;
}
int main()
{
int n;
scanf("%d",&n);
long long t[100001]={0};
int min,max,x;
scanf("%d",&x);
min=x;
max=x;
t[x]++;
int i;
for (i=2;i<=n;i++)
{
scanf("%d",&x);
t[x]++;
if (min>x) min=x;
if (max<x) max=x;
}
long long ans=0;
int a,b;
for (a=min;a<=max/2;a++)
{
if (t[a]==0) continue;
if (t[a]>=2 && t[2*a]!=0)
ans=(ans+C2(t[a])*C2(t[2*a]))%MOD;
for (b=a+1;b<=max-min;b++)
{
if (t[b]==0 || t[a+b]<2) continue;
ans=(ans+t[a]*t[b]%MOD*C2(t[a+b]))%MOD;
}
}
printf("%lld\n",ans);
return 0;
}
36-2 比例简化
题目描述
在社交媒体上,经常会看到针对某一个观点同意与否的民意调查以及结果。例如,对某一观点表示支持的有1498人,反对的有 902人,那么赞同与反对的比例可以简单的记为1498:902。
不过,如果把调查结果就以这种方式呈现出来,大多数人肯定不会满意。因为这个比例的数值太大,难以一眼看出它们的关系。对于上面这个例子,如果把比例记为5:3,虽然与真实结果有一定的误差,但依然能够较为准确地反映调查结果,同时也显得比较直观。
现给出支持人数A,反对人数B,以及一个上限L,请你将A比B化简为A’比B’,要求在A’和B’均不大于L且A’和B’互质(两个整数的最大公约数是1)的前提下,A’/B’≥ A/B且A’/B’- A/B的值尽可能小。
输入格式
共一行,包含三个整数A、B、L(1≤A≤1,000,000,1≤B≤1,000,000,1≤L≤100,A/B≤L),每两个整数之间用一个空格隔开,分别表示支持人数、反对人数以及上限。
输出格式
共一行,包含两个整数A’,B’,中间用一个空格隔开,表示化简后的比例。
输入样例
1498 902 10
输出样例
5 3
(1)编程思路。
由于L的范围不是很大(1≤L≤100),可以对简化后比例的分子i和分母j进行枚举。其中,1 ≤ i ≤ L,1 ≤ j ≤ L。
定义变量c和d保存结果。显然,i / j >= A / B,i / j < C / D。由于,A/B ≤ L,因此可设c和d的初始值分别为L和1。
为计算方便,将比例都转换为乘积的形式。即i / j >= A / B变化为i * B >= j * A,
i / j < C / D变化为i * D < j * C。
枚举i,j时,若满足i和j的最大公约数为1,且 i * B >= j * A && i * D < j * C,则i和j就是所求的答案。
(2)源程序。
#include <stdio.h>
int gcd(int m,int n)
{
int r;
r=m%n;
while (r!=0)
{
m=n;
n=r;
r=m%n;
}
return n;
}
int main()
{
int a,b,l;
scanf("%d%d%d", &a, &b, &l);
int i,j,c=l,d=1;
for (i=1; i<=l; i++)
{
for (j=1; j<=l; j++)
{
if(gcd(i, j)==1 && i * b >= j * a && i * d < j * c)
{
c=i;
d=j;
}
}
}
printf("%d %d", c, d);
return 0;
}
36-3 3个数的最大和
题目描述
给定 n 个正整数a1 …an,请从中选择 3 个数字,满足他们的和不大于给定的整数 m,请求出这个和最大可能是多少。
输入格式
第一行有两个整数,分别表示数字个数 n(1≤n≤100) 和给定的整数 m(6≤m≤3×105)。
第二行有 n 个整数,表示给定的 n 个数字 ai(1≤ai≤105)。
输出格式
输出一行一个整数表示答案。
输入样例
5 21
5 6 7 8 9
输出样例
21
(1)编程思路。
由于n不是很大,用3重循环进行简单穷举即可。
(2)源程序。
#include <stdio.h>
int main()
{
int n,m;
scanf("%d%d",&n,&m);
int b[101];
int i,j,k;
for (i=1;i<=n;i++)
scanf("%d",&b[i]);
int ans=0;
for (i=1;i<=n-2;i++)
for (j=i+1;j<=n-1;j++)
for (k=j+1;k<=n;k++)
{
int sum=b[i]+b[j]+b[k];
if (sum<=m && sum>ans) ans=sum;
}
printf("%d\n",ans);
return 0;
}