2 shunfurh shunfurh 于 2017.09.19 23:49 提问

Fermat vs. Pythagoras

Description

Computer generated and assisted proofs and verification occupy a small niche in the realm of Computer Science. The first proof of the four-color problem was completed with the assistance of a computer program and current efforts in verification have succeeded in verifying the translation of high-level code down to the chip level.
This problem deals with computing quantities relating to part of Fermat's Last Theorem: that there are no integer solutions of a^n + b^n = c^n for n > 2.
Given a positive integer N, you are to write a program that computes two quantities regarding the solution of x^2 + y^2 = z^2, where x, y, and z are constrained to be positive integers less than or equal to N. You are to compute the number of triples (x,y,z) such that x < y < z, and they are relatively prime, i.e., have no common divisor larger than 1. 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).
Input

The input consists of a sequence of positive integers, one per line. Each integer in the input file will be less than or equal to 1,000,000. Input is terminated by end-of-file
Output

For each integer N in the input file print two integers separated by a space. The first integer is the number of relatively prime triples (such that each component of the triple is <=N). The second number is the number of positive integers <=N that are not part of any triple whose components are all <=N. There should be one output line for each input line.
Sample Input

10
25
100
Sample Output

1 4
4 9
16 27

1个回答

caozhy
caozhy   Ds   Rxr 2017.10.05 09:29
已采纳
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
uva106 - Fermat vs. Pythagoras()
这道题暴力果断的不行啊, n会到达10^2,如果暴力的话,复杂度怎么也得O(n*n). 所以我们压根就不能对a,b,c中的任何数暴力, 但这里有个公式,我也是做了这道题才知道的。 (r*r-s*s)^2+(2*r*s)^2 = (r*r+s*s)^2; 我们只要枚举r和s即可。 效率大大提高了, 下面给出一位大神的证明: [解题方法]    该题可以归结为数论问题。
106 - Fermat vs. Pythagoras
此题实际上是求本原勾股数组(Primitive Pythagorean Triple, PPT)。稍用一点数论的经典知识就可以得到非常高效的解法。我的程序排名18,头一次进第一页:) 返回 Volume I 索引返回总索引 //////////////////////////////////////////////////////////////////////////
Fermat vs. Pythagoras
http://www.bnuoj.com/bnuoj/contest_show.php?cid=2322#problem/25802 // File Name: bo_jwolf4.cpp // Author: rudolf // Created Time: 2013年08月25日 星期日 13:47:10 #include #include #include #include #includ
UVaOJ106 - Fermat vs. Pythagoras
转载自http://www.cnblogs.com/devymex/archive/2010/08/07/1799713.html Time limit: 3.000 seconds 限时:3.000秒   Background 背景 Computer generated and assisted proofs and verification occupy a s
UVa 106 - Fermat vs. Pythagoras
题目:找到小于N的勾股数组的朴素解(三个数互质),并找到[1, N]中所有勾股数组中未出现过的数字个数。 分析:数论。这里直接利用《原本》中的解法即可。             x = 2st,y = s^2 - t^2,z = s^2 + t^2,             其中:1.s > t;(枚举顺序)                         2.s和t互质;(朴素解)  
poj 1305 Fermat vs. Pythagoras
毕达哥拉斯三元组 正整数
UVA 106 - Fermat vs. Pythagoras
关于毕达哥拉斯定理的数学题,由于要使得a和b互质需满足a和b必为一奇一偶,a,b,c满足存在正整数m,n, a = abs(m^2-n^2); b = 2mn c = m^2+n^2只要枚举m,n就行了#include#include#include#include#include#includeusing namespace std;const int MAXN=1000010;int gcd(
uva 106 - Fermat vs. Pythagoras
详细分析看:http://www.cnblogs.com/devymex/archive/2010/08/14/1799713.html#include #include #include using namespace std; bool flag[1000001]; int N; int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } int main() { while(cin >> N) { mem
POJ-1305(勾股定理)(Fermat vs. Pythagoras)
这个题目就是找在1~N之间互质的三个正整数x、y、z,并满足x^2+y^2=z^2,判断这样的数有多少对,以及跟1~N中与这些互质正整数无关的正整数的个数。 其实比较关键的是对上面那个式子 x^2+y^2=z^2 进行变形,减少一个变量为 (r^2-s^2)^2 + (2*r*s)^2 = (r^2+s^2)^2, 这样只有两个变量存在,可以减少一轮循环。于是题目就变成了找这样的r和s,当r
POJ 1305 Fermat vs. Pythagoras
大意:给定一个整数N,求N范围内(x,y,z 思路: 本原毕达哥拉斯方程组满足: x = m^2 - n^2; y = 2*m*n; z = m^2 + n^2; 其中m > n,且m,n奇偶性不同。 在此题中,要求所给范围内的毕达哥拉斯三元组,只需对m,n进行枚举即可,然后将三元组乘以i(保证i*z在所给的范围之内),就可以求出所有的毕达哥拉斯三元组。