import java.util.*; public class Euler660 { public static String solve() { long total = 0; for (int base = 9; base <= 18; base++) { int k = base / 3, rem = k - 1; long[] powBase = new long[k + 1]; powBase[0] = 1; for (int i = 1; i <= k; i++) powBase[i] = powBase[i - 1] * base; List states = new ArrayList<>(); int r = base % 3; long p = powBase[rem]; if (r == 0) { for (int a = 1; a < base; a++) for (int b = a + 1; b < base; b++) for (int c = b + 1; c < base; c++) { int mask = (1 << a) | (1 << b) | (1 << c); if (feasible(a, b, c, p, base)) states.add(new long[] { a, b, c, mask }); } } else if (r == 1) { for (int a = 1; a < base; a++) for (int b = a + 1; b < base; b++) { int mab = (1 << a) | (1 << b); for (int c1 = 1; c1 < base; c1++) if ((mab & (1 << c1)) == 0) for (int c0 = 0; c0 < base; c0++) { if (c0 == c1 || (mab & (1 << c0)) != 0) continue; long cv = c1 * base + c0; int mask = mab | (1 << c1) | (1 << c0); if (feasible(a, b, cv, p, base)) states.add(new long[] { a, b, cv, mask }); } } } else { for (int a = 1; a < base; a++) { int ma = 1 << a; for (int b1 = 1; b1 < base; b1++) { if ((ma & (1 << b1)) != 0) continue; for (int b0 = 0; b0 < base; b0++) { if (b0 == b1) continue; int mab = ma | (1 << b1) | (1 << b0); if (Integer.bitCount(mab) != 3) continue; long bv = b1 * base + b0; for (int c1 = 1; c1 < base; c1++) { if ((mab & (1 << c1)) != 0) continue; for (int c0 = 0; c0 < base; c0++) { if (c0 == c1 || (mab & (1 << c0)) != 0) continue; long cv = c1 * base + c0; if (bv >= cv) continue; int mask = mab | (1 << c1) | (1 << c0); if (feasible(a, bv, cv, p, base)) states.add(new long[] { a, bv, cv, mask }); } } } } } } for (int step = rem - 1; step > (rem > 3 ? 2 : rem - 1); step--) { List nxt = new ArrayList<>(); long pp = powBase[step]; for (long[] st : states) { long a = st[0], b = st[1], c = st[2]; int mask = (int) st[3]; for (int da = 0; da < base; da++) { if ((mask & (1 << da)) != 0) continue; for (int db = 0; db < base; db++) { if (db == da || (mask & (1 << db)) != 0) continue; for (int dc = 0; dc < base; dc++) { if (dc == da || dc == db || (mask & (1 << dc)) != 0) continue; int nm = mask | (1 << da) | (1 << db) | (1 << dc); long na = a * base + da, nb = b * base + db, nc = c * base + dc; if (feasible(na, nb, nc, pp, base)) nxt.add(new long[] { na, nb, nc, nm }); } } } } states = nxt; } if (rem == 2) { long p2 = (long) base * base; for (long[] st : states) { long a = st[0], b = st[1], c = st[2]; int mask = (int) st[3]; List digits = new ArrayList<>(); for (int d = 0; d < base; d++) if ((mask & (1 << d)) == 0) digits.add(d); if (digits.size() != 6) continue; int[] dd = digits.stream().mapToInt(Integer::intValue).toArray(); for (int[] perm : permutations6(dd)) { long fa = a * p2 + perm[0] * base + perm[1], fb = b * p2 + perm[2] * base + perm[3], fc = c * p2 + perm[4] * base + perm[5]; if (fa * fa + fb * fb + fa * fb == fc * fc && fc < fa + fb) total += fc; } } } else { long p3 = (long) base * base * base; int full = (1 << base) - 1; Map> byMask = new HashMap<>(); for (int d2 = 0; d2 < base; d2++) for (int d1 = 0; d1 < base; d1++) { if (d1 == d2) continue; for (int d0 = 0; d0 < base; d0++) { if (d0 == d1 || d0 == d2) continue; int v = d2 * base * base + d1 * base + d0, m = (1 << d2) | (1 << d1) | (1 << d0); // Pre-group by residue? Just store all tails byMask.computeIfAbsent(m, x -> new ArrayList<>()).add(new int[] { v, m }); } } // Simpler brute approach for remaining List tails = new ArrayList<>(); for (int d2 = 0; d2 < base; d2++) for (int d1 = 0; d1 < base; d1++) { if (d1 == d2) continue; for (int d0 = 0; d0 < base; d0++) { if (d0 == d1 || d0 == d2) continue; tails.add( new int[] { d2 * base * base + d1 * base + d0, (1 << d2) | (1 << d1) | (1 << d0) }); } } long mod3 = p3; Map> cByRes = new HashMap<>(); for (int i = 0; i < tails.size(); i++) cByRes.computeIfAbsent((long) tails.get(i)[0] * tails.get(i)[0] % mod3, x -> new ArrayList<>()) .add(i); Map> byMask2 = new HashMap<>(); for (int ai = 0; ai < tails.size(); ai++) { int av = tails.get(ai)[0], am = tails.get(ai)[1]; for (int bi = 0; bi < tails.size(); bi++) { int bv = tails.get(bi)[0], bm = tails.get(bi)[1]; if ((am & bm) != 0) continue; long res = ((long) av * av + (long) bv * bv + (long) av * bv) % mod3; int abm = am | bm; List cis = cByRes.get(res); if (cis == null) continue; for (int ci : cis) { int cv = tails.get(ci)[0], cm = tails.get(ci)[1]; if ((abm & cm) != 0) continue; int mk = abm | cm; byMask2.computeIfAbsent(mk, x -> new ArrayList<>()).add(new long[] { av, bv, cv }); } } } for (long[] st : states) { long a = st[0], b = st[1], c = st[2]; int mask = (int) st[3]; int remaining = full ^ mask; List entries = byMask2.get(remaining); if (entries == null) continue; for (long[] e : entries) { long fa = a * p3 + e[0], fb = b * p3 + e[1], fc = c * p3 + e[2]; if (fa * fa + fb * fb + fa * fb == fc * fc && fc < fa + fb) total += fc; } } } } return String.valueOf(total); } static boolean feasible(long a, long b, long c, long p, int base) { long mnA = a * p, mxA = a * p + p - 1, mnB = b * p, mxB = b * p + p - 1, mnC = c * p, mxC = c * p + p - 1; if (mnC >= mxA + mxB) return false; long ml = mxA * mxA + mxB * mxB + mxA * mxB, mnl = mnA * mnA + mnB * mnB + mnA * mnB; return ml >= mnC * mnC && mnl <= mxC * mxC; } static int[][] permutations6(int[] arr) { List result = new ArrayList<>(); perm6(arr, 0, result); return result.toArray(new int[0][]); } static void perm6(int[] arr, int idx, List result) { if (idx == arr.length) { result.add(arr.clone()); return; } for (int i = idx; i < arr.length; i++) { int t = arr[i]; arr[i] = arr[idx]; arr[idx] = t; perm6(arr, idx + 1, result); arr[idx] = arr[i]; arr[i] = t; } } public static void main(String[] args) { System.out.println(solve()); } }