精华内容
下载资源
问答
  • 勾股数公式

    2019-07-11 02:24:02
    现在他就遇到一个有趣的问题,比如,直角三角形的周长是120的话,那么它的三条边可以是20,48,52,或者24,45,51,还有30,40, 50,有三种不同的解,现在他想知道一个区间[a,b]中哪个的解最多(1<...
    话说已经三个月没碰过算法了,真的很无奈,恐怕学到的一点知识全忘光了。

    昨天,萝莉神给我一道题目:

     

    Title

     Roowe(没见过这么BT的,拿自己名字去编题目)很喜欢研究数学,现在他就遇到一个有趣的问题,比如,直角三角形的周长是120的话,那么它的三条边可以是20,48,52,或者24,45,51,还有30,40, 50,有三种不同的解,现在他想知道一个区间[a,b]中哪个数的解数最多(1<= a, b <= 1000000)?

    输入:
    10 100
    1000 100000
    1 1000000
    300000 700000
    100000 300000
    100000 700000
    800000 900000
    104 720720
    80 360360
    1 1000000
    输出:
    60 2
    55440 40
    720720 104
    360360 80
    240240 64
    360360 80
    831600 78
    720720 104
    360360 80

    720720 104

     

     

     让我做下,本来懒得做的,但是他说打表就OK了,于是我就欣然答应了。。。奈何他眼中的打表难易度和我眼中不一样,再次看到了数学系高材生和我的差距,嘿嘿。

         第一次尝试,失败。
        我说,不就是勾股定理a^2+b^2=c^2吗?结果他说,你再去补补数学知识。。。。
        于是给了我一个链接,我一看,不就是百度百科的勾股数吗,于是就暂时搁浅了。
        今晚第二次尝试,仍然失败。
        依稀记得昨天他给我说了有个什么勾股数公式,在百度百科那个勾股数的最下面介绍了,但是我看了半天,还是有点迷糊。
        然后让他把代码给我看看,好吧,结合百科介绍的勾股数公式,茅塞顿开。

       这里给出勾股数公式
       直角三角形三条边a, b, c,其中a,b是直角边。
       则 a=2*m*n   

             b=m^2-n^2   

             c=m^2+n^2

    当然,这是有前提条件的,也就是其局限性:“勾股数的公式还是有局限的。勾股数公式可以得到所有的基本勾股数,但是不可能得到所有的派生勾股数。比如6,8,10;9,12,15…,就不能全部有公式计算出来”

    也就是说,3,4,5可以求出来,但是其倍数6,8,10就不行了。

    这里要注意几个问题:

    1.构成三角形的条件:

         2*m*n+m^2-n^2 > m^2+n^2

         既m>n

    2.a, b, c互质,即无法得到派生的勾股数。

    以下是代码:

    // Tanky Woo
    // www.WuTianQi.com
    #include <iostream>
    #define M 1000000
    int arr[M+1];
    using namespace std;
     
    int gcd(int a, int b)
    {
        
    if(b==0)    
            
    return a;
        
    else     
            
    return gcd(b, a%b);
    }
     
    void init()
    {
        
    for(int i=1; i<=800++i)
            
    for(int j=i+12*j*j+2*j*i<=M; ++j)
            {
                    
    int x, y, z;
                    x
    =2*i*j;
                    y
    =j*j-i*i;
                    z
    =j*j+i*i;
                    
    //确保x,y,z互质 
                    if(gcd(gcd(x, y), z) == 1)
                    {
                        
    int t = x+y+z;
                        
    int tmp = 1;
                        
    while(tmp*<= M)
                        {
                            arr[tmp
    *t]++;
                            
    ++tmp;
                        }
                    }
            }
    }
     
    int main()
    {
        
    //freopen("input.txt","r",stdin);
        
    //freopen("output.txt","w",stdout);
        init();
        
    int n, m;
        
    while(scanf("%d%d",&n,&m) != EOF){
            
    int pos = 0;
            
    int Max = 0;
            
    for(int i=n; i<=m; i++){
                
    if(arr[i] > Max){
                    Max 
    = arr[i];
                    pos 
    = i;
                }
            }
            printf(
    "%d %d\n",pos, Max);
        }
        
    return 0;
    }

     

     Tanky Woo原创,转载请注明: 转载自Tanky Woo

    文章标题: 勾股数公式
    本文链接地址: http://www.wutianqi.com/?p=1632

    转载于:https://www.cnblogs.com/tanky_woo/archive/2010/12/03/1895286.html

    展开全文
  • Poj1305 勾股数公式

    2012-09-27 14:23:57
    这里给出勾股数公式:  直角三角形三条边a, b, c,其中a,b是直角边。  则 a=2*m*n  b=m^2-n^2  c=m^2+n^2 当然,这是有前提条件的,也就是其局限性:“勾股数的公式还是有局限的。勾股数公式可以得到所有...

    这里给出勾股数公式

       直角三角形三条边a, b, c,其中a,b是直角边。

        a=2*m*n

           b=m^2-n^2

           c=m^2+n^2

    当然,这是有前提条件的,也就是其局限性:勾股数的公式还是有局限的。勾股数公式可以得到所有的基本勾股数,但是不可能得到所有的派生勾股数。比如681091215…,就不能全部有公式计算出来

    也就是说,3,4,5可以求出来,但是其倍数6,8,10就不行了。

    这里要注意几个问题:

    1.构成三角形的条件:

         2*m*n+m^2-n^2 > m^2+n^2

         m>n

    2.a, b, c互质,即无法得到派生的勾股数。

    Poj1305求勾股数出现的次数

    题意:给出一个数n求出1-n中勾股数的个数,其中如果是倍数算一次,例如3 4 5,6 8 10 算一组。

    输出组数和1n中没有在勾股数中出现过的数字

    其中有一句是看了discuss才理解的

    You are also to compute the number of values 0 < p <= N such that p is not part of any triple (not just relatively prime triples

    意思是

    对于方程x^2 + y^2 = z^2有解(triples)为(x,y,z),p = |{k|k!=x && k!=y && k!=z for any(x,y,z) that fits x^2 + y^2 = z^2, k <= N, k为正整数}|

    #include<stdio.h>
    #include<math.h>
    #include<iostream>
    #include<string.h>
    #define M 1000000
    using namespace std;
    bool flag[1000005];
    __int64 gcd(__int64 a,__int64 b)
    {
    	if(b==0)
    		return a;
    	else
    		return gcd(b,a%b);
    }
    int main()
    {
    	__int64 n,s,t,a,b,c,ans1,ans2,i;
    	while(scanf("%I64d",&n)!=EOF)
    	{
    		ans1=0,ans2=0;
    		memset(flag,0,sizeof(flag));
    		for(t=1;t<=n;t++)
    		{
    			for(s=t+1; 2*s*s+2*s*t<=M; ++s)
    			{
    				a=2*s*t;
    				b=(s*s-t*t);
    				c=(s*s+t*t);
    				if(c>n)
    					break;
    				if(gcd(gcd(a,b),c)!=1)
    					continue;
    				ans1++;
    				for(i=1;c*i<=n;i++)
    				{
    					flag[i*a]=true;
    					flag[i*b]=true;
    					flag[i*c]=true;
    				}
    			}
    		}
    		for(i=1;i<=n;i++)
    			if(!flag[i])
    				ans2++;
    		printf("%I64d %I64d\n",ans1,ans2);
    	}
    	return 0;
    }
    


     

    展开全文
  •    

     

     

     

    展开全文
  • HDU 6441 Find Integer 题目 对于公式 an+bn=cna^n+b^n=c^nan+bn=cn。给出 n,a,找 b,c 的正整数解。不行输出-1 -1。 分析 ...当 n 等于 2,就变成了勾股定理 a2+b2=c2a^2+b^2=c^2a2+b2=c2。对于...

    HDU 6441 Find Integer

    题目

    对于公式 an+bn=cna^n+b^n=c^n。给出 n,a,找 b,c 的正整数解。不行输出-1 -1。

    分析

    首先给出的公式就是费马大定理。 当 n > 2时,没有正整数解。

    考虑 n = 0, 1, 2。前两种很容易得出。

    当 n 等于 2,就变成了勾股定理 a2+b2=c2a^2+b^2=c^2。对于勾股数的求解。有一个本原勾股数组。指勾股数中两两互质的勾股数,其他勾股数可以由其翻倍得出。

    公式:a=2mnb=m2n2c=m2+n2\begin{array}{l}{a= 2 m n} \\ {b=m^{2}-n^{2}} \\ {c=m^{2}+n^{2}}\end{array}
    令 n = 1,
    当 a 为偶数时,a=2m,b=(a/2)21,c=(a/2)2+1a = 2m, b = (a/2)^2-1,c = (a/2)^2+1

    当 a 为奇数时,方程两边除二:
    a=mb=(a21)/2c=(a2+1)/2\begin{array}{l}{a= m } \\ {b=(a^{2}-1)/2} \\ {c=(a^{2}+1)/2}\end{array}
    剩下的直接代公式。

    #include <bits/stdc++.h>
    using namespace std;
    #define ll long long 
    #define INF 0x3f3f3f3f
    #define fuck(x) cout<<x<<endl
    const int N = 1e5 + 5;
    const ll mod = 1e9 + 7;
    
    int t, n, a;
    
    int main(){
        scanf("%d", &t);
        while(t--){
            scanf("%d%d", &n, &a);
            if(n > 2 || n == 0){
                printf("-1 -1\n");
            }else if(n == 1){
                printf("1 %d\n", a + 1);
            }else{
                double x = a / 2.0;
                if(a%2){
                    printf("%.0lf %.0lf\n", a * x - 0.5, a * x + 0.5);
                }else{
                    printf("%.0lf %.0lf\n", x * x - 1, x * x + 1);
                }
            }
        }
        return 0;
    }
    
    /*
    
    */
    
    展开全文
  • 质因数分解: for(int i=2;i*i<=n;i++){ if(n%i==0) p.push_back(i); while(n%i==0) n/=i; } if(n!=1) p.push_back(n);...//欧拉函数 phi[x]代表[1,x]种与x互质的的个数 void getphi() { ...
  • 关于勾股数计算的两个新公式,庄严 ,庄宏飞,本文提出并证明了“勾股数通解公式”、“勾股数再生公式”,实现了全部勾股数的定a直求,这种只用算术运算就能得到三元二次方程a2
  • 勾股定理公式计算器是一款十分出色的勾股定理计算器,界面简洁,功能出众,支持两种计算器模式,基本模式和批量计算模式,计算方法非常的简单,在批量计算模式下,你只需在表格内输入基本信息,表格的最后一列将会...
  • 勾股定理公式计算器最新版是一款十分出色的勾股定理计算器,勾股定理公式计算器最新版界面简洁,功能出众,支持两种计算器模式,基本模式和批量计算模式,此外勾股定理公式计算器官方版的计算方法非常的简单,在批量...
  • 勾股数

    2014-06-24 00:23:00
    勾股数a^2+b^2=c^2可以写成a=n^2-m^2b=2*n*mc=n^2+m^2n>m>=1gcd(n,m)==1且n,m奇偶性不同!或a=(n^2-m^2)/2b=n*mc=(n^2+m^2)/2n>m>=1gcd(n,m)==1且n,m都为奇数!是勾股数组的整数倍的数组还是勾股数组...
  • 题意:给出N,x^2+y^2=z^2 小于等于N的解(互素...度娘给出勾股数的定义:只考虑互素的解,给出勾股数公式 a=2*m*n ,b=m*m-n*n ,c=m*m+n*n; 枚举m,n ,复杂度 O(log(N)^2) #include #include #include #include #i
  • 勾股数学习

    2013-05-14 09:57:00
    勾股数又名毕氏三元数凡是可以构成一个直角三角形三边的一组正整数,称之为勾股数。 编辑本段常用套路 简介 所谓勾股数,一般是指能够构成直角三角形三条边的三个正整数(a,b,c)。 即a2+b2=c2,a,...
  • 勾股数的性质

    2019-09-06 22:08:46
    如果正整数aa,bb,cc能满足不定方程a2+b2=c2a2+b2=c2,则它们叫一组勾股数,用[a,b,c][a,b,c]表示。 定义2 如果[a,b,c][a,b,c]为一勾股数组,且(a,b)=1(a,b)=1,则[a,b,c][a,b,c]叫一个勾股数的基本组;全体勾股数的...
  • 1.题意:给你a和n , 让你求 a^n + b^n = c^n 中b和c1,若无解输出-1,-1;若有解输出任意一组b,c ...(2)勾股数公式: 基本:a^2 + b^2 = c^2 拓展: 当a为大于1的奇数2n+1时,b=2n^2+2n,...
  • 1. 勾股数奇偶奇。 2. 勾股公式
  • 如何构造勾股数

    2018-08-25 20:45:00
    这里贴一下勾股数的构造:  当a为大于1的奇数2n+1时,b=2n2+2n, c=2n2+2n+1。  实际上就是把a的平方数拆成两个连续自然数,例如:  n=1时(a,b,c)=(3,4,5)  n=2时(a,b,c)=(5,12,13)  n=3时(a,b,c)=(7,24,25)  ...
  • 为叙述简便,把毕达哥拉斯三元组(Pythagorean Triples)称为勾股数。 另外,也可以参考《数学女孩2 费马大定理》第2章 勾股定理。 本原勾股数 本原勾股数(x,y,z)(x,y,z)(x,y,z)满足 x2+y2=z2x^2+y^2=z^2x2+y2=...
  • uva106(勾股数)

    2014-12-25 21:03:38
    问有多少互质的勾股数,然后除掉所有勾股数(包括不互质的),还剩几个数字. 根据公式 x^2 +y^2 = z^2则: x = i * i - j*j; y = 2*i* j; z = i*i + j * j; 遍历i,j就行了...
  • 费马大定理和勾股数

    2018-08-28 21:00:50
    若需要一組最小數為奇數的勾股數,可任意選取一個 3 或以上的奇數,將該數自乘為平方數,除以 2,答案加減 0.5 可得到 兩個新的數字,這兩個數字連同一開始選取的奇數,三者必定形成一組勾股數。但卻不一定是以這個...
  • 勾股数问题

    千次阅读 2010-06-07 22:43:00
    一.问题描述 如果直角三角形三条边长均为整数,这三个整数组成的数组就称为勾股数组,对于勾股数组(a,b,c),根据定理有关系式:a^2 + b^2=c^2 问题: 有一...递归算法: 设 a,b,c为一组勾股数, 设 m= c--a,有 a^2+(a+1)^2
  • 关于勾股数的规律

    2015-11-19 21:19:00
    前面部分还是不用看了,基本勾股数的构造可以直接跳到UPD部分  有可能是初中写的最后一篇了,中考啊~~ 以前跟一些人提到过,互质的勾股数a,b,c(即a²+b²=c²)都满足一个规律(其实互质满足了,那么不互质也一定...
  • 寻找勾股数算法的实现和优化 深夜隔壁寝室的老哥来访,说他用python实现的寻找2000以内勾股数的算法跑了20秒钟。邀请我一起讨论优化思路,完成后记录如下: 朴素探数法寻找勾股数 首先实现那个需要20秒钟的朴素...
  • 注:用a、b、c那三个公式求得的勾股数可能不全,应该还要利用如下性质: 如果 ( a ,  b ,  c ) 是勾股数,它们的正整数 倍数 ,也是勾股数,即 ( na ,  nb ,  nc ) 也是勾股数。 ...
  • UVA106 - Fermat vs. Pythagoras(素勾股数) 题目链接 题目大意:给你一个数n,勾股数三元组(x,y,z)的定义:满足x ...接着要换种方式构造素勾股数公式:x = m^2 - n^2; y = 2∗m∗n; z = m^2 + n^
  • 法里数列 性质1:连续三项为ba、b+da+c、dc\frac ba 、\...性质2:指定一个常数N,它的法里数列的项φ(N)\varphi(N)φ(N),因此可以得到前缀和是:φ(2)+φ(3)+⋯+φ(N)\varphi(2)+\varphi(3)+\dots+\varphi(N)...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,381
精华内容 952
关键字:

勾股数的公式