結果
問題 | No.1611 Minimum Multiple with Double Divisors |
ユーザー |
![]() |
提出日時 | 2021-07-21 21:42:22 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,613 ms / 2,000 ms |
コード長 | 1,059 bytes |
コンパイル時間 | 364 ms |
コンパイル使用メモリ | 81,664 KB |
実行使用メモリ | 77,656 KB |
最終ジャッジ日時 | 2024-10-03 02:23:29 |
合計ジャッジ時間 | 15,168 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 37 |
ソースコード
Primes_MAX = 10 ** 4 Primes = [] Sieve = [0] * Primes_MAX Sieve[0] = Sieve[1] = -1 for p in range(2, Primes_MAX): if not Sieve[p]: Primes.append(p) Sieve[p] = p for q in range(p * p, Primes_MAX, p): if not Sieve[q]: Sieve[q] = p def factorize(x): ret = [] while x != 1: p = Sieve[x] cnt = 0 while x % p == 0: x //= p cnt += 1 ret.append((p, cnt)) return ret for _ in range(int(input())): x = int(input()) for i in range(2, Primes_MAX): fs = factorize(i) pre = 1 for p, _ in fs: cnt = 0 tmp = x while tmp % p == 0: tmp //= p cnt += 1 pre *= 1 + cnt y = x * i nxt = 1 for p, _ in fs: cnt = 0 tmp = y while tmp % p == 0: tmp //= p cnt += 1 nxt *= 1 + cnt if 2 * pre == nxt: print(y) break