結果

問題 No.375 立方体のN等分 (1)
コンテスト
ユーザー tenten
提出日時 2020-12-04 18:02:32
言語 Java
(openjdk 23)
結果
TLE  
実行時間 -
コード長 2,937 bytes
コンパイル時間 2,757 ms
コンパイル使用メモリ 89,564 KB
実行使用メモリ 57,212 KB
最終ジャッジ日時 2024-09-15 04:51:27
合計ジャッジ時間 13,634 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 12 TLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.*;

public class Main {
    static HashMap<Long, Integer> map = new HashMap<>();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        long max = n;
        for (long i = 2; i <= Math.sqrt(n); i++) {
            while (n % i == 0) {
                map.put(i, map.getOrDefault(i, 0) + 1);
                n /= i;
            }
        }
        if (n > 1) {
            map.put(n, map.getOrDefault(n, 0) + 1);
        }
        HashSet<Unit> prev = new HashSet<>();
        prev.add(new Unit(1, 1, 1));
        for (long x : map.keySet()) {
            HashSet<Unit> tmp = new HashSet<>();
            for (int i = 0; i <= map.get(x); i++) {
                for (int j = 0; j <= map.get(x) - i; j++) {
                    tmp.add(new Unit(i, j, map.get(x) - i - j, x));
                }
            }
            HashSet<Unit> current = new HashSet<>();
            for (Unit u1 : prev) {
                for (Unit u2 : tmp) {
                    current.addAll(u1.add(u2));
                }
            }
            prev = current;
        }
        long min = max;
        for (Unit u : prev) {
            min = Math.min(min, u.getSum());
        }
       System.out.println(min + " " + (max - 1));
    }
    
    static class Unit {
        long[] arr = new long[3];
        
        public Unit(long a, long b, long c) {
            arr[0] = a;
            arr[1] = b;
            arr[2] = c;
            Arrays.sort(arr);
        }
        
        public Unit(int a, int b, int c, long x) {
            this(pow(x, a), pow(x, b), pow(x, c));
        }
        
        public HashSet<Unit> add(Unit another) {
            HashSet<Unit> ret = new HashSet<>();
            int[][] perm = new int[][]{{0, 1, 2}, {0, 2, 1}, {1, 0, 2}, {1, 2, 0}, {2, 0, 1}, {2, 1, 0}};
            for (int[] zz : perm) {
                ret.add(new Unit(arr[0] * another.arr[zz[0]], arr[1] * another.arr[zz[1]], arr[2] * another.arr[zz[2]]));
            }
            return ret;
        }
        
        public int hashCode() {
            return 0;
        }
        
        public boolean equals(Object o) {
            Unit u = (Unit) o;
            for (int i = 0; i < 3; i++) {
                if (arr[i] != u.arr[i]) {
                    return false;
                }
            }
            return true;
        }
        
        public long getSum() {
            long sum = 0;
            for (long x : arr) {
                sum += x - 1;
            }
            return sum;
        }
        
        public String toString() {
            return arr[0] + ":" + arr[1] + ":" + arr[2];
        }
    }
    
    static long pow(long x, int p) {
        if (p == 0) {
            return 1;
        } else if (p % 2 == 0) {
            return pow(x * x, p / 2);
        } else {
            return x * pow(x, p - 1);
        }
    }
}
0