（HDU6441）2018中国大学生程序设计竞赛 - 网络选拔赛 - 1004 - Find Integer - （费马大定理+勾股数）

本文主要是介绍（HDU6441）2018中国大学生程序设计竞赛 - 网络选拔赛 - 1004 - Find Integer - （费马大定理+勾股数），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6441

 

题意：T组样例，每组给出两个整数n，a，求出两个整数b，c满足：a^n+b^n=c^n；能找到b，c就输出，否则输出-1，-1。(1 ≤ T ≤ 1000000) (0 ≤ n ≤ 1000 000 000, 3 ≤ a ≤ 40000) (1 ≤ b, c ≤ 1000 000 000)。

解析：

①.很明显当n=0时无解；

②.当n=1时有a+b=c，那么随便取满足公式的b，c即可；

③.而由费马大定理知对于方程a^n+b^n=c^n当n>2时无解；

④.那么我们只需求一下n=2时方程a^2+b^2=c^2的解即可，题解上说用“费马大定理奇偶数列法则”，这里看到公式a^2+b^2=c^2的形式，想到用勾股数相关性质来解：

•         对于a^2+b^2=c^2，有如下套路：
•         1.当a为大于1的奇数2x+1时，b=2*x^2+2*x, c=2*x^2+2*x+1。
•         2.当a为大于4的偶数2x时，b=x^2-1, c=x^2+1。

资料：

• 费马大定理：https://baike.baidu.com/item/%E8%B4%B9%E9%A9%AC%E5%A4%A7%E5%AE%9A%E7%90%86/80363?fr=aladdin
• 勾股数：https://baike.baidu.com/item/%E5%8B%BE%E8%82%A1%E6%95%B0/2674064

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN=1000000000;int n,a,b,c;int main()
{int T;scanf("%d",&T);while(T--){scanf("%d%d",&n,&a);if(n==1){b=a;c=a*2;printf("%d %d\n",b,c);//printf("%d %d\n",1,a+1);}else if(n==2){int tn;if(a&1){tn=(a-1)/2;b=2*tn*tn+2*tn;c=2*tn*tn+2*tn+1;}else{tn=a/2;b=tn*tn-1;c=tn*tn+1;}printf("%d %d\n",b,c);}else{printf("%d %d\n",-1,-1);}}return 0;
}

 

 

这篇关于（HDU6441）2018中国大学生程序设计竞赛 - 网络选拔赛 - 1004 - Find Integer - （费马大定理+勾股数）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---