C语言程序设计100例之(36):四方定理

例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;

}

上一篇:【C学习笔记】day2-5 求两个数的最大公约数


下一篇:【PTA】【C语言】找二维数组中最大数及所在行列号