首页 > 代码库 > 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(素勾股数)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。