從維基百科的勾股數條目參考來的通解：
給一個任意數對(X,Y)，用以下公式代替
$A = X^2 – Y^2$
$B = 2XY$
$C = X^2 + Y^2$
得出的A,B,C就是一組勾股數。
若 (X,Y) 恰好互質而且一奇一偶，那麼會得到一組(A,B,C)互質的勾股數。
知道通解後，雙層迴圈跑 (X,Y) 就能找出所有互質勾股數。
按照台湾同胞的题解。 — 勾股数公式也是很神奇的啊。。。
此外还学习了bitset，因为是按位存储，所以比一般的bool来的更加迅速，也更加节省时间。
#include <iostream> #include <cstdio> #include <cstring> #include <set> #include <vector> #include <map> #include <algorithm> #include <queue> #include <cmath> #include <bitset> using namespace std; // 大数，内存处理 #define INF 0x3f3f3f3f #define ll long long int #define MEM(a) memset(a, 0, sizeof(a)) #define MEMM(a) memset(b, -1, sizeof(b)) #define DEB(x, n) cout << (x) << " " << (n) << endl const double PI = acos(-1.0); #define CR printf("\n") // 调试用 template <class Type> void debug(Type a[], int len) { for(int i = ; i < len ; i++) { cout << a[i] << " "; } cout << endl; } int gcd(int a, int b) { return a % b == ? b : gcd(b, a%b); } int odd(int a, int b) { return (a%2 && !(b%2)) || (b%2 &&!(a%2)); } int judge(int a, int b) { return (gcd(a, b) == 1 && odd(a, b)); } int n; const double eps = 1e-15; const int N = 1e6+10; bitset <N> p; int main() { #ifdef DEBUG // freopen("input", "r", stdin); //从input文件中读入 // freopen("output", "w", stdout); //输出到output文件 #endif while(~scanf("%d", &n)) { p.set(); int cnt = ; for(int x = 1; x < 1000; x ++) for(int y = x+1; ; y += 2) { int a, b, c; if(judge(x, y)) { a = y*y - x*x; b = 2*x*y; c = y*y + x*x; if(c > n) break; cnt ++; int ta = a, tb = b, tc = c; while(tc <= n) { p[ta] = p[tb] = p[tc] = ; ta += a, tb += b, tc += c; } } } int c2 = ; for(int i = 1;i <= n; i++) if(p[i]) c2++; printf("%d %d\n", cnt, c2); } return ; }