結果

問題 No.1611 Minimum Multiple with Double Divisors
コンテスト
ユーザー 小野寺健
提出日時 2021-11-17 15:28:05
言語 Java
(openjdk 23)
結果
TLE  
実行時間 -
コード長 1,864 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,464 ms
コンパイル使用メモリ 79,244 KB
実行使用メモリ 134,516 KB
最終ジャッジ日時 2024-12-23 15:17:42
合計ジャッジ時間 72,701 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 1
other AC * 8 WA * 10 TLE * 19
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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;
	}
	
}
0