Fermat vs. Pythagoras
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
Source
Duke Internet Programming Contest 1991,UVA 106
题目类型：本原毕达哥拉斯三元组
算法分析：直接暴力枚举val以内的所有m和n，判断构成三元组的情况并将三元组的倍数标记为True，最后累加[1,val]中没有被标记的数的个数
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 |
#include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> #define lson rt << 1, l, m #define rson rt << 1 | 1, m + 1, r using namespace std; const int INF = 0x7FFFFFFF; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int MOD = 7; const int maxn = 1000000 + 66; bool visited[maxn]; int gcd (int a, int b) { if (b == 0) return a; return gcd (b, a % b); } int main() { // ifstream cin ("aaa.txt"); int val; while (cin >> val) { memset (visited, false, sizeof (visited)); int ans1 = 0, ans2 = 0, x, y, z; int len = (int) sqrt (val + 0.0); int m, n; for (n = 1; n <= len; n++) { for (m = n + 1; m <= len; m++) { if (m * m + n * n > val) break; if (((n & 1) != (m & 1)) && (gcd (m, n) == 1)) { x = m * m - n * n; y = 2 * m * n; z = m * m + n * n; ans1++; int i; for (i = 1; ; i++) { if (i * z > val) break; visited[i*x] = visited[i*y] = visited[i*z] = true; } } } } cout << ans1; for (int i = 1; i <= val; i++) if (!visited[i]) ans2++; cout << " " << ans2 << endl; } return 0; } |
- « 上一篇：poj1300
- poj1316：下一篇 »