Tam giác "gần hoàn hảo"

Xem PDF

Tất cả bài nộp

Các bài nộp tốt nhất

Tác giả:

jumptozero

Dạng bài

Điểm: 300 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Tam giác \(K\) được gọi là tam giác "gần hoàn hảo" nếu \(K\) thỏa mãn \(2\) điều kiện sau:
Ba cạnh của tam giác đó có dạng \((a,a,b)\) thỏa mãn \(a>\frac{b}{2}\) và \(|a-b|=1\) với \(a,b\in \mathbb{N}^{*}\)
Diện tích của \(K\) là số nguyên dương.

Gọi \(Q\) là tập hợp tất cả các tam giác "gần hoàn hảo" .

Yêu cầu: Cho số nguyên dương \(N(1\leq N\leq 10^7)\) .Tính \(T=\sum\limits_{u\in Q\text{ và }P(u)\le N}P(u)\)

(trong đó: \(P(u)\) là chu vi của tam giác \(u\))

Nói cách khác, xét tất cả tam giác "gần hoàn hảo" và có chu vi không vượt quá \(N\). Hãy tính tổng chu vi tất cả tam giác đó.

Chú ý: Các tam giác có các cạnh \((a,a,b),(a,b,a),(b,a,a)\) thì cũng chỉ tính là \(1\) tam giác.

Input

Một dòng duy nhất chứa số nguyên dương \(N(1\leq N\leq 10^7)\)

Output

In ra đáp án \(T\) cần tìm.

Scoring

Subtask #1 (\(20\%\) số điểm): \(1\leq N\leq 300\)
Subtask #2 (\(80\%\) số điểm): Không có ràng buộc gì thêm

Example

Test 1

Input

Output

Note

Giải thích: Chỉ có duy nhất \(1\) tam giác "gần hoàn hảo" thỏa mãn yêu cầu bài toán đó là : \((5;5;6)\). Vậy nên đáp án là \(16\)

Bình luận

0

Kuroo 6:35 a.m. 6 Tháng 9, 2020

triệu hồi SPyofgame 🙁

Mình đang có vài vấn đề với editorial 😢 bạn xem tạm code ạ

C++

    ll res = 0;
    for (int a = 2; a * 3 - 1 <= n; ++a)
    {
        int AB = a;
        int AC = a;
        for (int b = a - 1; b <= a + 1; b += 2)
        {
            int P = 2 * a + b; /// chu vi tam giác
            if (P > n) break;

            int BC = b;
            if (b % 2 == 1) continue; /// BC chẵn <=> S = 1/2 * AH * HC nguyên dương

            int HC = b / 2;
            ll sqAH = 1LL * AC * AC - 1LL * HC * HC; /// sqAH = AH * AH
            if (isPerfectSquare(sqAH)) /// <=> S nguyên dương
                res += P;
        }
    }

0

SPyofgame 9:30 a.m. 6 Tháng 9, 2020

sure UwU

1 bình luận nữa