結果

問題 No.375 立方体のN等分 (1)
ユーザー tentententen
提出日時 2020-12-04 18:02:32
言語 Java21
(openjdk 21)
結果
TLE  
実行時間 -
コード長 2,937 bytes
コンパイル時間 3,882 ms
コンパイル使用メモリ 77,676 KB
実行使用メモリ 70,868 KB
最終ジャッジ日時 2023-10-13 07:34:57
合計ジャッジ時間 13,286 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 146 ms
57,192 KB
testcase_01 AC 146 ms
57,228 KB
testcase_02 AC 267 ms
62,760 KB
testcase_03 AC 148 ms
56,992 KB
testcase_04 AC 148 ms
57,156 KB
testcase_05 AC 147 ms
57,332 KB
testcase_06 AC 149 ms
57,088 KB
testcase_07 AC 159 ms
57,108 KB
testcase_08 AC 1,498 ms
63,120 KB
testcase_09 AC 152 ms
54,976 KB
testcase_10 AC 151 ms
57,068 KB
testcase_11 AC 154 ms
57,140 KB
testcase_12 AC 152 ms
56,728 KB
testcase_13 AC 151 ms
57,016 KB
testcase_14 TLE -
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 -- -
権限があれば一括ダウンロードができます

ソースコード

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