結果
| 問題 | No.1611 Minimum Multiple with Double Divisors |
| ユーザー |
 小野寺健
|
| 提出日時 | 2021-11-17 15:28:05 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 1,864 bytes |
| コンパイル時間 | 3,489 ms |
| コンパイル使用メモリ | 79,152 KB |
| 実行使用メモリ | 161,412 KB |
| 最終ジャッジ日時 | 2024-06-06 04:04:13 |
| 合計ジャッジ時間 | 10,855 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | -- | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
ソースコード
import java.util.Scanner;
import java.util.HashMap;
import java.util.Map;
import java.util.List;
import java.util.ArrayList;
import java.math.BigInteger;
public class No1611 {
public static void main(String[] args) {
memo = new HashMap<BigInteger, HashMap<BigInteger, Integer>>();
Scanner scan = new Scanner(System.in);
int T = Integer.valueOf(scan.nextLine());
List<String> X = new ArrayList<String>();
for (int i=0; i < T; i++) {
X.add(scan.nextLine());
}
scan.close();
for (String x : X) {
BigInteger bi = new BigInteger(x);
HashMap<BigInteger, Integer> f = prime_factor(bi);
int n = 1;
for (int i : f.values()) {
n *= i + 1;
}
BigInteger i = BigInteger.valueOf(2);
while (!multiple(n, f, prime_factor(i))) {
i = i.add(BigInteger.ONE);
}
System.out.println(bi.multiply(i));
}
}
private static HashMap<BigInteger, HashMap<BigInteger, Integer>> memo;
private static HashMap<BigInteger, Integer> prime_factor(BigInteger n) {
if (memo.containsKey(n)) {
return memo.get(n);
}
HashMap<BigInteger, Integer> res = new HashMap<BigInteger, Integer>();
for (BigInteger i = BigInteger.valueOf(2); i.multiply(i).compareTo(n) <= 0; i = i.add(BigInteger.ONE)) {
while (n.mod(i).equals(BigInteger.ZERO)) {
res.put(i, res.getOrDefault(i, 0) + 1);
n = n.divide(i);
}
}
if (!n.equals(BigInteger.ONE)) {
res.put(n, res.getOrDefault(n, 0) + 1);
}
memo.put(n, res);
return res;
}
private static boolean multiple(int n, HashMap<BigInteger, Integer> f0, HashMap<BigInteger, Integer> f1) {
int y = n;
for (Map.Entry<BigInteger, Integer> entry : f1.entrySet()) {
BigInteger k = entry.getKey();
int v = entry.getValue();
if (f0.containsKey(k)) {
int z = f0.get(k);
y = y / (z + 1) * (z + v + 1);
} else {
y *= v + 1;
}
}
return n * 2 == y;
}
}