結果
問題 |
No.1143 面積Nの三角形
|
ユーザー |
![]() |
提出日時 | 2025-03-31 17:35:04 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 72 ms / 800 ms |
コード長 | 2,063 bytes |
コンパイル時間 | 216 ms |
コンパイル使用メモリ | 82,256 KB |
実行使用メモリ | 76,652 KB |
最終ジャッジ日時 | 2025-03-31 17:36:12 |
合計ジャッジ時間 | 2,073 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
import math def factorize(n): factors = {} while n % 2 == 0: factors[2] = factors.get(2, 0) + 1 n //= 2 i = 3 while i * i <= n: while n % i == 0: factors[i] = factors.get(i, 0) + 1 n //= i i += 2 if n > 1: factors[n] = 1 return factors def generate_divisors(factors): divisors = [1] for p in factors: exp = factors[p] new_divisors = [] current_power = 1 for _ in range(exp + 1): for d in divisors: new_divisors.append(d * current_power) current_power *= p divisors = list(set(new_divisors)) # Remove duplicates divisors.sort() return divisors def main(): N = int(input().strip()) if N == 0: print(0) return K = N * N factors_n = factorize(N) # Prepare factors for N^2 (each exponent doubled) factors_k = {} for p in factors_n: factors_k[p] = factors_n[p] * 2 divisors = generate_divisors(factors_k) count = 0 for z in divisors: if z == 0: continue if K % z != 0: continue # Ensure divisibility, though should always be true Kz = K // z if Kz == 0: continue max_y = int(Kz ** (1/3)) + 2 # Estimate the cube root and add buffer max_y = min(max_y, Kz) # Ensure y doesn't exceed Kz y_start = z y_end = max_y for y in range(y_start, y_end + 1): if y == 0: continue if Kz % y != 0: continue q = Kz // y sum_yz = y + z D = sum_yz ** 2 + 4 * q s = math.isqrt(D) if s * s != D: continue numerator = (-sum_yz + s) if numerator <= 0: continue if numerator % 2 != 0: continue x = numerator // 2 if x >= y: count += 1 print(count) if __name__ == "__main__": main()