結果
| 問題 |
No.3301 Make Right Triangle
|
| ユーザー |
 kmmtkm
|
| 提出日時 | 2025-10-05 16:30:31 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 10,656 bytes |
| コンパイル時間 | 1,191 ms |
| コンパイル使用メモリ | 116,076 KB |
| 実行使用メモリ | 20,324 KB |
| 最終ジャッジ日時 | 2025-10-05 16:30:58 |
| 合計ジャッジ時間 | 5,751 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | -- * 1 |
| other | WA * 1 TLE * 1 -- * 7 |
ソースコード
// 自作ライブラリ
// https://github.com/takumi-okamoto/competitive-programming-public/tree/main/mylib
#include <iostream>
#include <cmath>
#include <string>
#include <numeric> // For std::gcd
#include <vector>
#include <sstream>
/*
Original Python Code:
# 自作ライブラリ
# https://github.com/takumi-okamoto/competitive-programming-public/tree/main/mylib
import sys
import math
# sys.setrecursionlimit(10**8)
def debug(*args):
print(*args, file=sys.stderr)
def solve(l):
if l in [3, 4, 5]:
return "3 4 5"
# a = k(m**2-n**2)
# b = 2kmn
# c = k(m**2 + n**2)
# gcd(m, n) = 1
m = 1
while m * m < l:
# lが素数の場合
# m ** 2 + n ** 2 = l
n2 = l - m * m
n1 = int(n2**0.5)
for d in [-1, 0, 1]:
n = n1 + d
if n * n == n2:
break
else:
n = None
if n is not None:
g = math.gcd(m, n)
k = g**2
m = m // g
n = n // g
if m > n:
return f"{k*(m**2 - n**2)} {2*k*m*n} {k*(m**2+n**2)}"
m += 1
n = 1
while 2 * n * n <= l:
if l % (2 * n) == 0:
m = l // (2 * n)
if m > n:
g = math.gcd(m, n)
m //= g
n //= g
k = g * g
return f"{k*(m**2 - n**2)} {2*k*m*n} {k*(m**2+n**2)}"
n += 1
d = 1
while d * d <= l:
if l % d == 0:
if (l // d - d) % 2 == 0:
n = (l // d - d) // 2
m = 2 * n + d
if m > n:
g = math.gcd(m, n)
m //= g
n //= g
k = g * g
return f"{k*(m**2 - n**2)} {2*k*m*n} {k*(m**2+n**2)}"
d += 1
def main():
t = int(input())
ans = []
for _ in range(t):
ans.append(solve(int(input())))
print(*ans, sep="\n")
# for abc in ans:
# a, b, c = map(int, abc.split())
# assert a**2 + b**2 == c**2
if __name__ == "__main__":
main()
*/
// The Python `debug` function printing to stderr is omitted as it is for debugging, not part of the core algorithm.
using namespace std;
// For simplicity and to match the Python usage of integers, we'll use long long for calculations to prevent overflow.
using ll = long long;
/**
* @brief Translates the Python `solve` function.
* * The algorithm attempts to find a Pythagorean triple (a, b, c) such that
* a + b + c = L (represented as `l` in the code). The logic is based on
* Euclid's formula for generating Pythagorean triples:
* a = k(m^2 - n^2), b = 2kmn, c = k(m^2 + n^2), where gcd(m, n) = 1 and m > n.
* The perimeter L is then: L = a + b + c = 2k m (m + n).
* The code searches for integers m, n, and k that satisfy the equation for a given L.
* * The three main search loops correspond to different ways of factoring the perimeter L.
* The time complexity remains the same: dominated by the first loop which runs
* up to $\sqrt{L}$ iterations, and the second and third loops running up to $\sqrt{L}$.
* Thus, the complexity is $O(\sqrt{L})$, which is preserved.
* * @param l The perimeter L of the Pythagorean triple.
* @return A string with "a b c" of the found triple, or potentially an empty string if no solution is found (though the problem context implies one should exist or the function logic ensures it).
*/
string solve(ll l) {
// Handle the base case l in [3, 4, 5]
if (l == 3 || l == 4 || l == 5) {
return "3 4 5";
}
// --- First loop: Based on L = k(m^2 + n^2) - This part seems to be an incorrect interpretation
// of the perimeter formula in the original Python code's comment, but the logic
// m^2 + n^2 = l is tested for finding prime-perimeter triples where k=1.
// The loop searches for an L that is the hypotenuse (c) of a primitive triple (k=1).
ll m = 1;
while (m * m < l) {
// lが素数の場合 (The comment suggests looking for prime L, but the logic applies generally)
// m ** 2 + n ** 2 = l
ll n2 = l - m * m;
if (n2 <= 0) { // Should not happen given m*m < l, but for safety
m++;
continue;
}
// Equivalent to n1 = int(n2**0.5)
ll n1 = (ll)round(sqrt((double)n2));
ll n = 0; // Initialize n to 0
bool found_n = false;
// Equivalent to: for d in [-1, 0, 1]:
for (ll d = -1; d <= 1; ++d) {
ll temp_n = n1 + d;
if (temp_n > 0 && temp_n * temp_n == n2) {
n = temp_n;
found_n = true;
break;
}
}
// Equivalent to: if n is not None: (i.e., if found_n is true and n > 0)
if (found_n && n > 0) {
// Check if m and n form a primitive triple component.
// g = math.gcd(m, n)
ll g = std::gcd(m, n);
// k = g**2
ll k = g * g;
// m = m // g
ll m_prime = m / g;
// n = n // g
ll n_prime = n / g;
// The original logic uses the modified m and n to calculate the triple,
// which effectively sets k' = g^2 and uses the *reduced* primitive pair (m', n').
if (m_prime > n_prime) {
ll a = k * (m_prime * m_prime - n_prime * n_prime);
ll b = 2 * k * m_prime * n_prime;
ll c = k * (m_prime * m_prime + n_prime * n_prime);
// C++ equivalent to f-string formatting
stringstream ss;
ss << a << " " << b << " " << c;
return ss.str();
}
}
m++;
}
// --- Second loop: Based on L = 2k m (m + n). Here the code looks for factors 2n such that L/(2n) = m is an integer.
// This simplifies the perimeter formula for the case where L = 2kmn and m+n is the other factor,
// or more directly: L is factorized as L = (2n) * m'. The structure suggests the code is
// effectively testing L = 2n * m for a potential pair (m, n) from Euclid's formula.
m = 0; // Reset m for this loop
ll n_l2 = 1; // Used instead of 'n' to avoid re-using the loop variable name from the first loop, but semantically is the 'n' in Euclid's formula.
while (2 * n_l2 * n_l2 <= l) {
// If 2n divides l
if (l % (2 * n_l2) == 0) {
// m = l // (2 * n)
m = l / (2 * n_l2);
if (m > n_l2) {
// g = math.gcd(m, n)
ll g = std::gcd(m, n_l2);
ll m_prime = m / g;
ll n_prime = n_l2 / g;
ll k = g * g; // k = g * g
// Calculate and return the triple (a, b, c) using the reduced pair (m', n') and k'.
ll a = k * (m_prime * m_prime - n_prime * n_prime);
ll b = 2 * k * m_prime * n_prime;
ll c = k * (m_prime * m_prime + n_prime * n_prime);
// C++ equivalent to f-string formatting
stringstream ss;
ss << a << " " << b << " " << c;
return ss.str();
}
}
n_l2++;
}
// --- Third loop: Based on L = 2k m (m + n). Factorizing L as L = d * d' where d = 2k(m+n) and d' = m. No, the Python logic is:
// L = d * d' where d is a divisor. The code sets:
// m - n = d' (or d) and m + n = d (or d').
// Since L = 2k m (m+n), the factorization L = d * d' here is used to find factors d and d' such that
// d * d' = L, and from there infer m and n.
// The code assumes that $L$ is decomposed into $L = (m-n) \times (m+n)$ which is incorrect for perimeter,
// but the logic `(l // d - d) % 2 == 0` is characteristic of factoring $L = d \times d'$ and
// finding $m, n$ from $d'$ and $d$. Let $A = m^2-n^2 = (m-n)(m+n)$. If $L$ is a side $A$, then:
// $m-n = d$ and $m+n = l/d$.
// $n = (l/d - d) / 2$ and $m = n + d$. This is the exact logic used, implying the function
// *also* attempts to find an $L$ that is a side of the triple, specifically $a = k(m^2-n^2) = L$.
ll d = 1;
while (d * d <= l) {
if (l % d == 0) {
ll d_prime = l / d;
// Test if d_prime - d is even. This is necessary for $n$ to be an integer.
// (l // d - d) % 2 == 0
if ((d_prime - d) % 2 == 0) {
// n = (l // d - d) // 2
ll n_l3 = (d_prime - d) / 2;
// m = 2 * n + d => m = n + (n+d) -> m = n + l/d - n -> m = l/d - n. No, the Python code is correct:
// m = n + d' = (l/d - d)/2 + d = (l/d - d + 2d)/2 = (l/d + d)/2.
// The Python code is m = 2*n + d. If n=(l/d - d)/2, then 2n = l/d - d.
// m = (l/d - d) + d = l/d. The Python code is equivalent to: m = l / d.
// Let's stick to the Python's explicit calculation:
m = 2 * n_l3 + d;
if (m > n_l3) {
// g = math.gcd(m, n)
ll g = std::gcd(m, n_l3);
ll m_prime = m / g;
ll n_prime = n_l3 / g;
ll k = g * g; // k = g * g
// Calculate and return the triple (a, b, c) using the reduced pair (m', n') and k'.
ll a = k * (m_prime * m_prime - n_prime * n_prime);
ll b = 2 * k * m_prime * n_prime;
ll c = k * (m_prime * m_prime + n_prime * n_prime);
// C++ equivalent to f-string formatting
stringstream ss;
ss << a << " " << b << " " << c;
return ss.str();
}
}
}
d++;
}
// FAILED: The original Python code does not have an explicit return path if no solution is found in the loops.
// Based on the problem context of AtCoder, a solution is expected to be found.
return "FAILED";
}
void main_func() {
// Standard I/O for AtCoder contests
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t;
if (!(cin >> t)) return;
vector<string> ans;
for (ll i = 0; i < t; ++i) {
ll l;
if (!(cin >> l)) break;
ans.push_back(solve(l));
}
// Print all answers separated by newlines
for (const string& result : ans) {
cout << result << "\n";
}
}
int main() {
main_func();
return 0;
}