結果
| 問題 | No.3663 LCM Decomposition |
| コンテスト | |
| ユーザー |
|
| 提出日時 | 2026-11-20 01:36:33 |
| 言語 | PyPy3 (8.0.1 + ACL) |
| 結果 |
TLE
不安定
|
| 実行時間 | - |
| コード長 | 2,569 bytes |
| 記録 | |
| コンパイル時間 | 88 ms |
| コンパイル使用メモリ | 64,704 KB |
| 実行使用メモリ | 118,244 KB |
| 最終ジャッジ日時 | 2026-11-20 01:36:46 |
| 合計ジャッジ時間 | 11,444 ms |
|
ジャッジサーバーID (参考情報) |
judge1_0 / judge3_0 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 9 TLE * 3 -- * 4 |
ソースコード
# https://yukicoder.me/problems/no/3663
import math
def prime_decomp(N):
sqrt_n = int(math.sqrt(N))
p_map = {}
for p in range(2, sqrt_n + 1):
if N % p == 0:
cnt = 0
while N % p == 0:
cnt += 1
N //= p
p_map[p] = cnt
if N > 1:
p_map[N] = 1
return p_map
def get_divisors(N):
sqrt_n = int(math.sqrt(N))
divisors = []
for p in range(1, sqrt_n + 1):
if N % p == 0:
q = N // p
divisors.append(p)
if q != p:
divisors.append(q)
return divisors
def solve(N, L, R):
p_map = prime_decomp(N)
divisors = get_divisors(N)
p_array = [(p, e) for p, e in p_map.items()]
p_array.sort(key=lambda x: x[0])
p_array2 = [p ** e for p, e in p_array]
target_divisors_map = {}
for d in divisors:
if L <= d <= R:
bit = 0
for i in range(len(p_array2)):
if d % p_array2[i] == 0:
bit |= 1 << i
if bit not in target_divisors_map:
target_divisors_map[bit] = []
if len(target_divisors_map[bit]) <= 3:
target_divisors_map[bit].append(d)
target_divisors = []
for bit, ar in target_divisors_map.items():
for d in ar:
target_divisors.append((d, bit))
prevs = [{} for _ in range(len(target_divisors) + 1)]
prevs[0][(0, 0)] = -1
for index in range(len(target_divisors)):
d, bit = target_divisors[index]
for key in prevs[index].keys():
count, current_bit = key
prevs[index + 1][key] = (key, d)
if count <= 2:
new_count = count + 1
new_bit = current_bit | bit
prevs[index + 1][(new_count, new_bit)] = (key, d)
target_key = (3, 2 ** len(p_array2) - 1)
if target_key in prevs[-1]:
key = target_key
answer = []
for i in reversed(range(1, len(target_divisors) + 1)):
p = prevs[i][key]
next_key, d = p
if next_key[0] < key[0]:
answer.append(d)
key= next_key
answer.sort()
return " ".join(map(str, answer))
else:
return -1
def main():
T = int(input())
answers = []
for _ in range(T):
N, L, R = map(int, input().split())
ans = solve(N, L, R)
answers.append(ans)
for ans in answers:
print(ans)
if __name__ == "__main__":
main()