UVA106 - Fermat vs. Pythagoras（素勾股数）

本文主要是介绍UVA106 - Fermat vs. Pythagoras（素勾股数），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

UVA106 - Fermat vs. Pythagoras（素勾股数）

题目链接

题目大意:给你一个数n，勾股数三元组（x,y,z)的定义：满足x < y < z, x^2 + y^2 = z^2.现在问这里里面有多少个三元组是素勾股数即满足x，y， z两两互质。并且判断剩下的1-n的数有多少是没有出现在勾股数三元组中。

解题思路：先找出所有的素勾股数(x, y, z) ,那么便可以通过（kx， ky, kz)得到不是素勾股数的勾股数。接着要换种方式构造素勾股数，公式：x = m^2 - n^2; y = 2∗m∗n; z = m^2 + n^2；其中若 m 和 n 是互质，而且 m 和 n 其中有一个是偶数，计算出来的 x, y, z就是素勾股数。这样可以将遍历的范围缩小1000.

代码：

#include <cstdio>
#include <cstring>
#include <cmath>const int maxn = 1e6 + 5;int vis[maxn];
int n;int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);
}int solve () {int x, y, z;int m = sqrt(n);int count = 0;memset (vis, 0, sizeof (vis));for (int i = 1; i <= m; i++) {for (int j = i + 1; j <= m; j += 2) {x = j * j - i * i;y = 2 * i * j;z = j * j + i * i;if (x > n || y > n || z > n)continue;if (x * x + y * y == z * z && gcd(i, j) == 1) {//            printf ("%d %d %d\n", x, y, z);count++;for (int k = 1; k * z <= n; k++)vis[k * x] = vis[k * y] = vis[k * z] = 1;}}}return count;
}int main () {while (scanf ("%d", &n) == 1) {int c = solve();int p = 0;for (int i = 1; i <= n; i++)if (!vis[i]) {p++;
//                printf ("%d\n", i);}printf ("%d %d\n", c, p);}return 0;
}

这篇关于UVA106 - Fermat vs. Pythagoras（素勾股数）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---