FZU1669 Right-angled Triangle【毕达哥拉斯三元组】

2024-06-15 05:18

本文主要是介绍FZU1669 Right-angled Triangle【毕达哥拉斯三元组】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目链接:

http://acm.fzu.edu.cn/problem.php?pid=1669


题目大意:

求满足以a、b为直角边,c为斜边,并且满足a + b + c <= L的直角三角形的个数。


思路:

勾股定理,a、b、c也就是本原毕达哥拉斯三元组,则满足:

x = m^2 - n^2

y = 2*m*n

z = m^2 + n^2

其中m > n,且若m为奇数,则n为偶数,若m为偶数,则n为奇数。

枚举m、n,然后将三元组乘以i倍,保证 i * (x + y + z)在所给范围内(2 * m^2 + 2 * m*n <= L),

就可以求出所有满足条件的三元组。


AC代码:

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;bool flag[1001000];int GCD(int a,int b)
{if(b == 0)return a;return GCD(b,a%b);
}int main()
{int N;while(cin >> N){int temp,m,n,i,ans,x,y,z;ans = 0;memset(flag,false,sizeof(flag));temp = sqrt(N*1.0);for(n = 1; n <= temp; ++n){for(m = n+1; m <= temp; ++m){if(2*m*m + 2*m*n > N)break;if((n&1) != (m&1)){if(GCD(m,n) == 1){x = m*m - n*n;y = 2*m*n;z = m*m + n*n;for(int i = 1; ; ++i){if(i*(x+y+z) > N)break;ans++;}}}}}cout << ans << endl;}return 0;
}


这篇关于FZU1669 Right-angled Triangle【毕达哥拉斯三元组】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1062528

相关文章

leetCode#119. Pascal's Triangle II

Description Given an index k, return the kth row of the Pascal’s triangle. For example, given k = 3, Return [1,3,3,1]. Note: Could you optimize your algorithm to use only O(k) extra space? Code

Csting Left Mid Right

 CString Left( int nCount ) const;                   //从左边1开始获取前 nCount 个字符 CString Mid( int nFirst ) const;                      //从左边第 nCount+1 个字符开始,获取后面所有的字符 CString Mid( int nFirst, int nC

第六篇——黄金分割:毕达哥拉斯如何连接数学和美学?

目录 一、背景介绍二、思路&方案三、过程1.思维导图2.文章中经典的句子理解3.学习之后对于投资市场的理解4.通过这篇文章结合我知道的东西我能想到什么? 四、总结五、升华 一、背景介绍 人眼看到的美的东西,都可以从数学这个抽象的学科中得到明确的逻辑论证;这就是数学学科神奇的地方之一 二、思路&方案 1.思维导图2.文章中经典的句子理解3.学习之后对于投资市场的理解4.通过这篇

CodeForces 407A Triangle

题意: 一个直角三角形所有点都在二维平面整点上  其中两条边长度分别为a和b  且没有任何一条边与坐标轴平行  问  这样的三角形存不存在  如果存在输出一组坐标 思路: 可以设解存在  然后先固定(0,0)这个点  这样就可以求出所有满足边长是a和b的(x,y)坐标分别放在两个数组里 注意只枚举第一、二象限即可  要不还要防止三点共线 枚举a和b的所有解  如果这确定的三个点满足

力扣刷题--1534. 统计好三元组【简单】

题目描述 给你一个整数数组 arr ,以及 a、b 、c 三个整数。请你统计其中好三元组的数量。 如果三元组 (arr[i], arr[j], arr[k]) 满足下列全部条件,则认为它是一个 好三元组 。 0 <= i < j < k < arr.length |arr[i] - arr[j]| <= a |arr[j] - arr[k]| <= b |arr[i] - arr[k]| <

National Contest for Private Universities (NCPU), 2019 E. Generalized Pascal's Triangle

编辑代码 2000ms 262144K Generalized Pascal's Triangle Pascal's triangle is a triangular array in which each number can be calculated by the sum of the two numbers directly above that number as shown i

NLP-信息抽取:关系抽取【即:三元组抽取,主要用于抽取实体间的关系】【基于命名实体识别、分词、词性标注、依存句法分析、语义角色标注】【自定义模板/规则、监督学习(分类器)、半监督学习、无监督学习】

信息抽取主要包括三个子任务: 实体抽取与链指:也就是命名实体识别关系抽取:通常我们说的三元组(triple)抽取,主要用于抽取实体间的关系事件抽取:相当于一种多元关系的抽取 一、关系抽取概述 关系抽取通常在实体抽取与实体链指之后。在识别出句子中的关键实体后,还需要抽取两个实体或多个实体之间的语义关系。语义关系通常用于连接两个实体,并与实体一起表达文本的主要含义。常见的关系抽取结果

join连接的五种方式的简单使用案例(Inner join,Left join,Right join,Full join,Cross join)

1.内连接Inner join 内连接是基于连接谓词将俩张表(如A和B)的列组合到一起产生新的结果表  ,在表中存在至少一个匹配时,INNER JOIN 关键字返回行。    下面是一个简单的使用案例  以下是运行代码及结果  2.左外连接Left join 左外连接Left join关键字会从左表那里返回所有的行,即使是在右表中没有匹配到的行    下面是一个简单的案例

UVA 11401 Triangle Counting

中文详解请访问我的博客:http://xiaoshig.sinaapp.com/?p=128 You are given n rods of length 1, 2…, n. You have to pick any 3 of them & build a triangle. How many distinct triangles can you make? Note that, two

Leetcode211: Populating Next Right Pointers in Each Node II

Follow up for problem "Populating Next Right Pointers in Each Node". What if the given tree could be any binary tree? Would your previous solution still work? Note: You may only use constant e