POJ 1305 Fermat vs. Pythagoras(勾股数)

本文主要是介绍POJ 1305 Fermat vs. Pythagoras(勾股数)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：LINK 

题意： 求[1,n]内本原勾股数(PPT)(a, b, c 没有公因数，满足a^2 + b^2 == c^2)。和范围内不被任何勾股数组包含的数的数量.
勾股数组定理: 每个本原勾股数组(a, b, c) (a为奇数， b为偶数) 可以这样得到
    a = s*t; 
    b = (s*s - t*t) /2; 
    c = (s*s + t*t) /2; 
    s > t >=1 ，s, t是任意没有公因数的奇数.
    因此可以根据这种方法进行构造.

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<cmath>
using namespace std;
#define INF 1000000000
#define N 1000005
int n;
int vis[N];
int gcd(int a, int b)
{if(!b) return a;return gcd(b, a%b);
}
int main()
{
#ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin);
#endif // ONLINE_JUDGEwhile(scanf("%d", &n) != EOF ) {int out = 0;memset(vis, 0, sizeof(vis));for(int i = 1; i*i/2 <= n; i+=2) {for(int j = i+2; (i*i + j*j)/2 <=n; j+=2) {if(gcd(i, j)!= 1) continue;int a = i*j;int b = (j*j - i*i) /2;int c = (i*i + j*j) /2;out ++;for(int k = 1; c*k<=n; k++) {vis[a*k] = vis[b*k] = vis[c*k] = 1;}}}int gg = 0;for(int i=1; i<=n; i++) {if(!vis[i]) gg++;}printf("%d %d\n", out, gg);}return 0;
}

这篇关于POJ 1305 Fermat vs. Pythagoras(勾股数)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---