uva 106 - Fermat vs. Pythagoras(素勾股数） - c++编程基础

题目大意：给出n，计算n以内有多少对素勾股数，并计算出n以内有多少数可以用来组成勾股数。

解题思路：暴力应该是会超时，本题肯定是考查勾股数的性质，上维基查了一下勾股数，上面讲的很清楚，只要将构造方法实现就好了。

#include   
#include   
#include   
const int N = 1000010;  
  
bool vis[N];  
  
long long gcd(long long a, long long b) {  
    return b == 0   a : gcd(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 (gcd(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;  
}