Всем привет! С этой задачкой я сижу уже неделю, застряла окончательно, поэтому прошу помощи в ускорении программы. Я читала самый популярный комментарий, и именно оттуда взяла идею с матрицей степеней. Но вот остальное решение я не могу понять. Хочется не просто повторить за человеком, а понять, почему оно так работает. Буду очень благодарна, если объясните или бросите в меня названием алгоритма или чего-то такого, что можно почитать на эту тему. Потому что я что только ни читала за эту неделю - все не о том. Спасибо!
package com.javarush.task.task20.task2025;
import java.util.*;
/*
Алгоритмы-числа
*/
public class Solution {
static List<Long> list = new ArrayList<>();
static int[][] powers;
public static long[] getNumbers(long N) {
fillPowers();
if(N <= 0) {
return new long[0];
}
list.clear();
long res = 0L;
for (long i = 1L; i < N; i++) {
int t = getDigitFromLong(i);
long temp = i;
while (temp >= 1) {
long devidedIntoTen = temp % 10;
res += powers[t] [(int) devidedIntoTen];
temp/=10;
}
if(res == i) {
list.add(res);
res = 0;
} else {
res = 0;
}
}
Collections.sort(list);
long[] l = new long[list.size()];
for (int i = 0; i < list.size(); i++) {
l[i] = list.get(i);
}
return l;
}
public static void fillPowers() {
int numDigits = getDigitFromLong(Long.MAX_VALUE);
powers = new int[numDigits][10];
for (int i = 0; i < numDigits; i++) {
for (int j = 0; j < 10; j++) {
powers[i][j] = (int) Math.pow(j, i);
}
}
}
public static int getDigitFromLong (long number) {
int numDigits = 0;
while (number > 0) {
number /= 10;
numDigits++;
}
return numDigits;
}
public static void main(String[] args) {
long a = System.currentTimeMillis();
System.out.println(Arrays.toString(getNumbers(1000)));
long b = System.currentTimeMillis();
System.out.println("memory " + (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory()) / (8 * 1024));
System.out.println("time = " + (b - a) / 1000);
a = System.currentTimeMillis();
System.out.println(Arrays.toString(getNumbers(Long.MAX_VALUE)));
b = System.currentTimeMillis();
System.out.println("memory " + (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory()) / (8 * 1024));
System.out.println("time = " + (b - a) / 1000);
}
}