poj1305

maksyuki 发表于 oj 分类，标签: 数论-毕达哥拉斯三元组

15 9月 2015

Fermat vs. Pythagoras

Computer generated and assisted proofs and verification occupy a small niche in the realm of Computer Science. The first proof of the four-color problem was completed with the assistance of a computer program and current efforts in verification have succeeded in verifying the translation of high-level code down to the chip level. This problem deals with computing quantities relating to part of Fermat's Last Theorem: that there are no integer solutions of a^n + b^n = c^n for n > 2.
Given a positive integer N, you are to write a program that computes two quantities regarding the solution of x^2 + y^2 = z^2, where x, y, and z are constrained to be positive integers less than or equal to N. You are to compute the number of triples (x,y,z) such that x < y < z, and they are relatively prime, i.e., have no common divisor larger than 1. You are also to compute the number of values 0 < p <= N such that p is not part of any triple (not just relatively prime triples).

Input

The input consists of a sequence of positive integers, one per line. Each integer in the input file will be less than or equal to 1,000,000. Input is terminated by end-of-file

Output

For each integer N in the input file print two integers separated by a space. The first integer is the number of relatively prime triples (such that each component of the triple is <=N). The second number is the number of positive integers <=N that are not part of any triple whose components are all <=N. There should be one output line for each input line.

Sample Input

100

Sample Output

1 4

4 9

16 27

Source

Duke Internet Programming Contest 1991,UVA 106

题目类型：本原毕达哥拉斯三元组

算法分析：直接暴力枚举val以内的所有m和n，判断构成三元组的情况并将三元组的倍数标记为True，最后累加[1,val]中没有被标记的数的个数

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int MOD = 7;
const int maxn = 1000000 + 66;

bool visited[maxn];

int gcd (int a, int b)
{
    if (b == 0)
        return a;

return gcd (b, a % b);
}


int main()
{
//    ifstream cin ("aaa.txt");

    int val;

    while (cin >> val)
    {
        memset (visited, false, sizeof (visited));

        int ans1 = 0, ans2 = 0, x, y, z;

        int len = (int) sqrt (val + 0.0);

        int m, n;
        for (n = 1; n <= len; n++)
        {
            for (m = n + 1; m <= len; m++)
            {
                if (m * m + n * n > val)
                    break;

                if (((n & 1) != (m & 1)) && (gcd (m, n) == 1))
                {
                    x = m * m - n * n;
                    y = 2 * m * n;
                    z = m * m + n * n;
                    ans1++;

                    int i;
                    for (i = 1; ; i++)
                    {
                        if (i * z > val)
                            break;

                        visited[i*x] = visited[i*y] = visited[i*z] = true;
                    }
                }
            }
        }

        cout << ans1;
        for (int i = 1; i <= val; i++)
            if (!visited[i])
                ans2++;

        cout << " " << ans2 << endl;
    }

return 0;
}

100

101

102

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int MOD = 7;

const int maxn = 1000000 + 66;

bool visited[maxn];

int gcd (int a, int b)

{

if (b == 0)

return a;

return gcd (b, a % b);

}

int main()

{

// ifstream cin ("aaa.txt");

int val;

while (cin >> val)

{

memset (visited, false, sizeof (visited));

int ans1 = 0, ans2 = 0, x, y, z;

int len = (int) sqrt (val + 0.0);

int m, n;

for (n = 1; n <= len; n++)

{

for (m = n + 1; m <= len; m++)

{

if (m * m + n * n > val)

break;

if (((n & 1) != (m & 1)) && (gcd (m, n) == 1))

{

x = m * m - n * n;

y = 2 * m * n;

z = m * m + n * n;

ans1++;

int i;

for (i = 1; ; i++)

{

if (i * z > val)

break;

visited[i*x] = visited[i*y] = visited[i*z] = true;

}

cout << ans1;

for (int i = 1; i <= val; i++)

if (!visited[i])

ans2++;

cout << " " << ans2 << endl;

}

return 0;

}

poj1300

poj1316

一	二	三	四	五	六	日
« 6月
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30

超客的水墨烟雨

poj1305

分类目录

标签云

书签

近期评论