勾股数组

      一般地,若三角形三边长a,b,c都是正整数,且满足a,b的平方和等于c的平方,那么数组(a,b,c)称为勾股数组。勾股数组是人们为了解出满足勾股定理的不定方程的所有整数解而创造的概念。       再来看下面这些勾股数:(3,4,5),(5,12,13),(7,24,25),(9,40,41),(11,60,61)…这些勾股数都是以奇数为一边构成的直角三角形。由以上已知任意一个大于2的偶数可以构成一组勾股数,实际上以任意一个大于1的奇数2n+1(n>1)为边也可以构成勾股数,其三边分别是2n+1、2n^2+2n、2n^2+2n+1,这可以通过勾股定理的逆定理获证。                                                                                                                                         ———以上来自百度百科


      由以上已知任意一个大于2的偶数可以构成一组勾股数,实际上以任意一个大于1的奇数2n+1(n>1)为边也可以构成勾股数,其三边分别是2n+1、2n^2+2n、2n^2+2n+1,这可以通过勾股定理的逆定理获证。        上面这句话是重点句,也就是说,我们只要能得到一个大于2的数,就可以得到一个勾股数组。下面用一道题来练习一下(2018中国大学生程序设计竞赛 - 网络选拔赛的1004题) 题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6441

Find Integer

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 6597    Accepted Submission(s): 1852 Special Judge

Problem Description

people in USSS love math very much, and there is a famous math problem . give you two integers nnn,aaa,you are required to find 222 integers bbb,ccc such that anana^{n}+bn=cnbn=cnb^{n} = c^{n} .

Input

one line contains one integer TTT;(1≤T≤1000000)(1≤T≤1000000)(1 \le T\le1000000) next TTT lines contains two integers nnn,aaa;(0≤n≤1000(0≤n≤1000(0 \le n \le1000,000000000,000,3≤a≤40000)000,3≤a≤40000)000,3 \le a \le 40000)

Output

print two integers bbb,ccc if bbb,ccc exits;(1≤b,c≤1000(1≤b,c≤1000(1 \le b,c \le 1000,000000000,000)000)000); else print two integers -1 -1 instead.

Sample Input

1
2 3

Sample Output

4 5

      这道题的题意是有一个公式a^n + b^n = c^n,输入n和a,然后求出b和c的值,没有的话输出-1 -1。首先由费马大定理可得当n大于2的时候是无解的,所以我们只需要去讨论当n等于0、1、2这三种情况就好了,当n等于0的时候易知无解,当n等于1的时候我们只需要输出1 a+1就好了。当n等于2的时候就是上面所说的要去求一个勾股数组,当a为奇数有勾股数(2*a+1,2*a*a+2*a,a*a+1);当a为偶数有勾股数(2*a,a*a-1,a*a+1)。


AC代码:

#include <bits/stdc++.h>
using namespace std;
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 if(n == 2){
                if(a % 2 == 1){
                    int ans = (a - 1) / 2;
                    printf("%d %d\n",ans * ans + (ans+1) * (ans+1) - 1,ans * ans + (ans+1) * (ans+1));
                }
                else{
                    int ans = (a + 2) / 2;
                    printf("%d %d\n",(ans - 1) * (ans - 1) - 1,(ans-1) * (ans-1) + 1);
                }
            }
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏码匠的流水账

聊聊flink LocalEnvironment的execute方法

flink-java-1.6.2-sources.jar!/org/apache/flink/api/java/DataSet.java

16620
来自专栏Java架构

Java并发编程:AbstractQueuedSynchronizer的内部结构

  虽然已经有很多前辈已经分析过AbstractQueuedSynchronizer(简称AQS,也叫队列同步器)类,但是感觉那些点始终是别人的,看一遍甚至几遍...

9610
来自专栏IT可乐

JDK1.8源码(九)——java.util.LinkedHashMap 类

  前面我们介绍了 Map 集合的一种典型实现  HashMap  ,关于 HashMap 的特性,我们再来复习一遍:

10420
来自专栏计算机视觉战队

深度学习的昨天、今天和明天

机器学习是人工智能领域的一个重要学科。 自从20世纪80年代以来, 机器学习在算法、理论和应用等方面都获得巨大成功。2006年以来, 机器学习领域中一个叫“ 深...

12030
来自专栏java一日一条

优秀Java程序员必须了解的GC工作原理

一个优秀的Java程序员必须了解GC的工作原理、如何优化GC的性能、如何与GC进行有限的交互,因为有一些应用程序对性能要求较高,例如嵌入式系统、实时系统等,只有...

21740
来自专栏陈树义

JVM系列第8讲:JVM 垃圾回收机制

在第 6 讲中我们说到 Java 虚拟机的内存结构,提到了这部分的规范其实是由《Java 虚拟机规范》指定的,每个 Java 虚拟机可能都有不同的实现。其实涉及...

13340
来自专栏行者常至

021.使用反射,编写SpringIOC

就是把每一个bean(实体类)与bean(实体类)之间的关系交给第三方容器进行管理。 而不是传统的在你的对象内部直接控制。

9820
来自专栏JAVA高级架构

基于zookeeper和quartz实现分布式定时调度

利用zookeeper的特性,来控制quartz实现分布式调度,保证quartz的单点运行,同时解除quartz自身分布式部署对数据库的依赖,保证同一时刻只有一...

30520
来自专栏赵俊的Java专栏

LeetCode 557 Reverse Words in a String III

首先按照空格对字符串进行分隔,然后将每个单词进行翻转后再拼接回字符串即可,需要注意拼接时记得加空格,但最后一个单词不需要加。

10910
来自专栏赵俊的Java专栏

LeetCode 344 Reverse String

8720

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励