uva 106 - Fermat vs. Pythagoras(素勾股数)
题目大意:给出n,计算n以内有多少对素勾股数,并计算出n以内有多少数可以用来组成勾股数。解题思路:暴力应该是会超时,本题肯定是考查勾股数的性质,上维基查了一下勾股数,上面讲的很清楚,只要将构造方法实现就好了。
#include <stdio.h> #include <string.h> #include <math.h> const int N = 1000010; bool vis[N]; long long 易做图(long long a, long long b) { return b == 0 ? a : 易做图(b, a % b); } int main () { long long a, b, c, n, cntans, cntuse; while (scanf("%lld", &n) == 1) { cntans = cntuse = 0; memset(vis, 0, sizeof(vis)); long long m = (long long)sqrt(n + 0.5); for (long long t = 1; t <= m; t += 1) { for (long long s = t + 1; s * t <= n; s += 2) { if (易做图(s, t) == 1) { a = s * t * 2; b = (s * s - t * t); c = (s * s + t * t); if (c <= n) { cntans++; if (!vis[a]) { cntuse++; vis[a] = 1; } if (!vis[b]) { cntuse++; vis[b] = 1; } if (!vis[c]) { cntuse++; vis[c] = 1; } } for (int i = 2; c * i <= n; i++) { if (!vis[a * i]) { cntuse++; vis[a * i] = 1; } if (!vis[b * i]) { cntuse++; vis[b * i] = 1; } if (!vis[c * i]) { cntuse++; vis[c * i] = 1; } } } } } printf("%lld %lld\n", cntans, n - cntuse); } return 0; }
补充:软件开发 , C++ ,