ACM – Uva106 – 勾股定理

点击量:23

從維基百科的勾股數條目參考來的通解:
給一個任意數對(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 = 0; i < len ; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;
}
int gcd(int a, int b) { return a % b == 0 ? 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 = 0;
        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] = 0;
                        ta += a, tb += b, tc += c;
                    }
                }
            }
        int c2  = 0;
        for(int i = 1;i <= n; i++)
            if(p[i]) c2++;
        printf("%d %d\n", cnt, c2);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注