fzu1669

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

12 9月 2015

Problem Description

A triangle is one of the basic shapes of geometry: a polygon with three corners or vertices and three sides or edges which are line segments. A triangle with vertices A, B, and C is denoted △ABC.

Triangles can also be classified according to their internal angles, described below using degrees of arc:

A right triangle (or right-angled triangle, formerly called a rectangled triangle) has one 90° internal angle (a right angle). The side opposite to the right angle is the hypotenuse; it is the longest side in the right triangle. The other two sides are the legs or catheti (singular: cathetus) of the triangle. Right triangles conform to the Pythagorean Theorem, wherein the sum of the squares of the two legs is equal to the square of the hypotenuse, i.e., a^2 + b^2 = c^2, where a and b are the legs and c is the hypotenuse.
An oblique triangle has no internal angle equal to 90°.
An obtuse triangle is an oblique triangle with one internal angle larger than 90° (an obtuse angle).
An acute triangle is an oblique triangle with internal angles all smaller than 90° (three acute angles). An equilateral triangle is an acute triangle, but not all acute triangles are equilateral triangles.

What we consider here is very simple. Give you the length of L, you should calculate there are how many right-angled triangles such that a + b + c ≤ L where a and b are the legs and c is the hypotenuse. You should note that the three numbers a, b and c are all integers.

Input

There are multiply test cases. For each test case, the first line is an integer L(12≤L≤2000000), indicating the length of L.

Output

For each test case, output the number of right-angled triangles such that a + b + c ≤ L where a and b are the legs and c is the hypotenuse.

Sample Input

Sample Output

Hint

There are five right-angled triangles where a + b + c ≤ 40. That are one right-angled triangle where a = 3, b = 4 and c = 5; one right-angled triangle where a = 6, b = 8 and c = 10; one right-angled triangle where a = 5, b = 12 and c = 13; one right-angled triangle where a = 9, b = 12 and c = 15; one right-angled triangle where a = 8, b = 15 and c = 17.

Source

FOJ月赛-2008年11月

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

算法分析：直接按照定理构建本原的毕达哥拉斯三元组，然后直接除本原的毕达哥拉斯三元组的和累加到res即可

#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>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define i64 long long

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

long long gcd (long long a, long long b)
{
    if (b == 0)
        return a;
    return gcd (b, a % b);
}


int main()
{
//    CPPFF;

    long long val;
    while (cin >> val)
    {
        long long tt = (long long ) sqrt (val + 0.0);
        long long res = 0, x, y, z, ta;

        for (long long n = 1; n <= tt; n++)
        {
            for (long long m = n + 1; m <= tt; m++)
            {
                if (2 * m * m + 2 * m * n > val)
                    break;

                if (gcd (n, m) == 1 && (n % 2 != m % 2))
                {
                    x = m * m - n * n;
                    y = 2 * m * n;
                    z = m * m + n * n;
                    ta = val / (x + y + z);
                    res += ta;
                }
            }
        }
        cout << res << endl;
    }
    return 0;
}

#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>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define i64 long long

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-6;

const double PI = 2 * acos (0.0);

const int maxn = 1e6 + 66;

long long gcd (long long a, long long b)

{

if (b == 0)

return a;

return gcd (b, a % b);

}

int main()

{

// CPPFF;

long long val;

while (cin >> val)

{

long long tt = (long long ) sqrt (val + 0.0);

long long res = 0, x, y, z, ta;

for (long long n = 1; n <= tt; n++)

{

for (long long m = n + 1; m <= tt; m++)

{

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

break;

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

{

x = m * m - n * n;

y = 2 * m * n;

z = m * m + n * n;

ta = val / (x + y + z);

res += ta;

}

cout << res << endl;

}

return 0;

}

acdream1077

fzu1759

一	二	三	四	五	六	日
« 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

超客的水墨烟雨