C语言程序设计100例之（36）：四方定理

例36   四方定理

题目描述

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

输入格式

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

输出格式

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

输入样例

2003

输出样例

48

        （1）编程思路1。

        设n=a²+b²+c²+d²，用4重循环对a、b、c、d的取值组合进行穷举。其中

        0≤a≤sqrt(n)  ，  a≤b≤sqrt(n)  ，  b≤c≤sqrt(n)  ，  c≤d≤sqrt(n)

（2）源程序1。

#include

#include

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

          for (b=a;b

            for (c=b;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

#include

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

            for (b=a; b

                for (c=b; c

                {

                    if (a*a+b*b+c*c>=n)

                        break;

                    d=sqrt(n-a*a-b*b-c*c);

                    if (d

                        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

#include

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×10⁵）。

第二行 n 个整数，第 i 个整数 ai （0≤ai≤5×10³）代表第 i 根木棒的长度。

输出格式

一行一个整数代表答案。

输入样例

1 1 2 2

输出样例

        （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

#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

    }

    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

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×10⁵）。

第二行有 n 个整数，表示给定的 n 个数字 ai（1≤ai≤10⁵）。

输出格式

输出一行一个整数表示答案。

输入样例

5 21

5 6 7 8 9

输出样例

21

         （1）编程思路。

         由于n不是很大，用3重循环进行简单穷举即可。

        （2）源程序。

#include

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;

}