Числа слишком велики для переменных

Вам не нужно хранить такой большой номер, вам нужны только последние десять цифр. Вы можете хранить это в долгом.

Эффективный способ вычисления больших степеней - это умножение и квадраты, например 19 ^ 19 = 19 * 19 ^ 2 * 19 ^ 16 = 19 * 19 ^ 2 * 19 ^ 2 ^ 2 ^ 2 ^ 2. Если у вас есть значение больше 10 ^ 10, вы можете обрезать последние 10 цифр.

Кстати, последние десять цифр 1000 ^ 1000 - это 0000000000, и когда вы добавляете это к своей сумме, это то же самое, что и добавление нуля;)

Изменить: хотя вам не нужно использовать BigInteger, его проще написать.

BigInteger tenDigits = BigInteger.valueOf(10).pow(10);
BigInteger sum = BigInteger.ZERO;
for (int i= 1; i <= 1000; i++) {
    BigInteger bi = BigInteger.valueOf(i);
    sum = sum.add(bi.modPow(bi, tenDigits));
}
sum = sum.mod(tenDigits);

modPow более эффективен, чем pow с mod по отдельности, поскольку ему не нужно вычислять очень большие числа, а только результат mod.

Вы можете использовать BigIntegers ...

public static void main(String[] args) {
    BigInteger acc = BigInteger.ZERO;

    for (int k = 1; k <= 1000; k++) {
        BigInteger pow = BigInteger.valueOf(k).pow(k);
        acc = acc.add(pow);
    }

    System.out.println(acc);
}

Я считаю, что проблема исходит от Project Euler, так что это не просто математическая задача; это также должно потребовать некоторых вычислений. Я не знаю, как это можно решить карандашом и бумагой, кроме как путем копирования вычислений, которые может произвести компьютер. Я не вижу многого в чисто математическом решении. Однако математика может помочь нам оптимизировать код.

Чтобы поднять ^ n, найдите двоичное расширение n:

n = n_k x 2^k + n_(k-1) x 2^(k-1) + ... + n_0 x 2^0 

где n_i = 0 or 1 - двоичные цифры n с нулевой цифрой справа. потом

a^n = a^(n_k x 2^k) x a^(n_(k-1) x 2^(k-1)) x ... x a^(n_0 x 2^0). 

Мы можем игнорировать любые факторы, где n_i = 0, поскольку тогда коэффициент равен a^0 = 1. Процесс можно записать в виде алгоритма O(log n) времени и O(1) пространства (см. Ниже).

Далее, в качестве проблемы, чтобы избежать использования BigInteger, мы можем разбить вычисление на две части: найти ответ mod 2^10 и найти ответ mod 5^10. В обоих случаях числа в соответствующих диапазонах и произведения чисел в соответствующих диапазонах укладываются в longs. Обратной стороной является то, что мы должны использовать китайскую теорему об остатках, чтобы рекомбинировать результаты, но это не так сложно и поучительно. Самая сложная часть использования китайской теоремы об остатках - это найти обратные mod m, но это можно сделать простым способом, используя модификацию алгоритма Евклида.

Асимптотическое время работы O(n log n), пространство O(1), и все умещается в несколько long переменных, никаких BigInteger или другой сложной библиотеки не требуется.

public class SeriesMod1010 {

  public static long pow(long a,long n,long m) { // a^n mod m
    long result = 1;
    long a2i = a%m; // a^2^i for i = 0, ...
    while (n>0) {
      if (n%2 == 1) {
    result *= a2i;
    result %= m;
      }
      a2i *= a2i;
      a2i %= m;
      n /= 2;
    }
    return result;
  }

  public static long inverse(long a, long m) { // mult. inverse of a mod m
    long r = m;
    long nr = a;
    long t = 0;
    long nt = 1;
    long tmp;
    while (nr != 0) {
      long q = r/nr;
      tmp = nt; nt = t - q*nt; t = tmp;
      tmp = nr; nr = r - q*nr; r = tmp;
    }
    if (r > 1) return -1; // no inverse
    if (t < 0) t += m;
    return t;
  }

  public static void main(String[] args) {
    long twoTo10 = 1024;
    long sum210 = 0;
    for (long i=1; i<=1000; i++) {
      sum210 += pow(i,i,twoTo10);
      sum210 %= twoTo10;
    }

    long fiveTo10 = 9_765_625;
    long sum510 = 0;
    for (long i=1; i<=1000; i++) {
      sum510 += pow(i,i,fiveTo10);
      sum510 %= fiveTo10;
    }

    // recombine the numbers with the Chinese remainder theorem
    long tenTo10 = 10_000_000_000L;
    long answer = sum210 * inverse(fiveTo10,twoTo10) * fiveTo10
      + sum510 * inverse(twoTo10,fiveTo10) * twoTo10;
    answer %= tenTo10;
    System.out.println(answer);
  }

}

используйте BigIntegers:

    import java.math.BigInteger;

public class Program {

    public static void main(String[] args) {
        BigInteger result = new BigInteger("1");
        BigInteger temp = new BigInteger("1");
        BigInteger I;
        for(int i = 1 ; i < 1001 ; i++){
            I = new BigInteger(""+i);
            for(int j = 1 ; j < i ; j++){
                temp = temp.multiply(I);
            }
            result = result.multiply(temp);
            temp = new BigInteger("1");
        }
        System.out.println(result);
    }
}

Ее можно решить без BigInteger, потому что вам нужно хранить только 10 последних цифр при каждой операции сложения или умножения, используя %, чтобы избежать переполнения:

int n = 1000;
long result = 0;
long tenDigits = 10_000_000_000L;
for (int i = 1; i <= n; i++) {
    long r = i;
    for (int j = 2; j <= i; j++) {
        r = (r * i) % tenDigits;
    }
    result += r;
}  
return result % tenDigits;

Сложность O (N ^ 2), предполагается, что умножение выполняется за постоянное время.

Ответ: 9110846700.

Десятичная основа использует 0 ... 9 (10 цифр) для представления цифр, число, которое находится во второй позиции справа налево, представляет Digits * base.length ^ l2rPosition. Используя эту логику, вы можете создать класс, который «в значительной степени выполняет то, что сказал вам учитель начальной школы, когда мы использовали бумагу для вычислений, но с числом baseN и преобразованиями от основания к основанию». Я выполнил этот класс полностью функционален на C #, но у меня нет времени полностью переводить его на java, это примерно та же логика, что и java.math.BigInteger. (с меньшей производительностью, держу пари, я использовал много списков> _> "Нет времени оптимизировать его сейчас

class IntEx {
    ArrayList<Integer> digits = new ArrayList<>();
    long baseSize = Integer.MAX_VALUE+1;
    boolean negative = false;

    public IntEx(int init)
    {
        set(init);
    }

    public void set(int number)
    {
        digits = new ArrayList<>();
        int backup = number;
        do
        {
            int index = (int)(backup % baseSize);
            digits.add(index);
            backup = (int) (backup / baseSize);
        } while ((backup) > 0);
    }

    // ... other operations
    private void add(IntEx number)
    {
        IntEx greater = number.digits.size() > digits.size() ? number : this;
        IntEx lesser = number.digits.size() < digits.size() ? number : this;
        int leftOvers = 0;
        ArrayList<Integer> result = new ArrayList<>();
        for (int i = 0; i < greater.digits.size() || leftOvers > 0; i++)
        {
            int sum;
            if (i >= greater.digits.size())
                sum = leftOvers;
            else if(i >= lesser.digits.size())
                sum = leftOvers + greater.digits.get(i);
            else
                sum = digits.get(i) + number.digits.get(i) + leftOvers;
            leftOvers = 0;
            if (sum > baseSize-1)
            {
                while (sum > baseSize-1)
                {
                    sum -= baseSize;
                    leftOvers += 1;
                }
                result.add(sum);
            }
            else
            {
                result.add(sum);
                leftOvers = 0;
            }
        }
        digits = result;
    }
    private void multiply(IntEx target)
    {
        ArrayList<IntEx> MultiParts = new ArrayList<>();
        for (int i = 0; i < digits.size(); i++)
        {
            IntEx thisPart = new IntEx(0);
            thisPart.digits = new ArrayList<>();
            for (int k = 0; k < i; k++)
                thisPart.digits.add(0);
            int Leftovers = 0;
            for (int j = 0; j < target.digits.size(); j++)
            {
                int multiFragment = digits.get(i) * (int) target.digits.get(j) + Leftovers;
                Leftovers = (int) (multiFragment / baseSize);
                thisPart.digits.add((int)(multiFragment % baseSize));
            }
            while (Leftovers > 0)
            {
                thisPart.digits.add((int)(Leftovers % baseSize));
                Leftovers = (int) (Leftovers / baseSize);
            }
            MultiParts.add(thisPart);
        }
        IntEx newNumber = new IntEx(0);
        for (int i = 0; i < MultiParts.size(); i++)
        {
            newNumber.add(MultiParts.get(i));
        }
        digits = newNumber.digits;
    }

    public long longValue() throws Exception
    {
        int position = 0;
        long multi = 1;
        long retValue = 0;
        if (digits.isEmpty()) return 0;
        if (digits.size() > 16) throw new Exception("The number within IntEx class is too big to fit into a long");
        do
        {
            retValue += digits.get(position) * multi;
            multi *= baseSize;
            position++;
        } while (position < digits.size());
        return retValue;
    }

    public static long BaseConvert(String number, String base)
    {
        boolean negative = number.startsWith("-");
        number = number.replace("-", "");
        ArrayList<Character> localDigits = new ArrayList<>();
        for(int i = number.toCharArray().length - 1; i >=0; i--) {
            localDigits.add(number.charAt(i));
        }
        // List<>().reverse is missing in this damn java. -_-
        long retValue = 0;
        long Multi = 1;
        char[] CharsBase = base.toCharArray();
        for (int i = 0; i < number.length(); i++)
        {
            int t = base.indexOf(localDigits.get(i));
            retValue += base.indexOf(localDigits.get(i)) * Multi;
            Multi *= base.length();
        }
        if (negative)
            retValue = -retValue;
        return retValue;
    }

    public static String BaseMult(String a, String b, String Base)
    {
        ArrayList<String> MultiParts = new ArrayList<>();
        // this huge block is a tribute to java not having "Reverse()" method.
        char[] x = new char[a.length()];
        char[] y = new char[b.length()];
        for(int i = 0; i < a.length(); i++) {
            x[i] = a.charAt(a.length()-i);
        }
        for(int i = 0; i < b.length(); i++) {
            y[i] = a.charAt(a.length()-i);
        }
        a = new String(x);
        b = new String(y);
        // ---------------------------------------------------------------------
        for (int i = 0; i < a.length(); i++)
        {
            ArrayList<Character> thisPart = new ArrayList<>();
            for (int k = 0; k < i; k++)
                thisPart.add(Base.charAt(0));
            int leftOvers = 0;
            for (int j = 0; j < b.length(); j++)
            {
                // Need I say repeated characters in base may cause mayhem?
                int MultiFragment = Base.indexOf(a.charAt(i)) * Base.indexOf(b.charAt(j)) + leftOvers;
                leftOvers = MultiFragment / Base.length();
                thisPart.add(Base.charAt(MultiFragment % Base.length()));
            }
            while (leftOvers > 0)
            {
                thisPart.add(Base.charAt(leftOvers % Base.length()));
                leftOvers = leftOvers / Base.length();
            }
            char[] thisPartReverse = new char[thisPart.size()];
            for(int z = 0; z < thisPart.size();z++)
                thisPartReverse[z] = thisPart.get(thisPart.size()-z);
            MultiParts.add(new String(thisPartReverse));
        }
        String retValue = ""+Base.charAt(0);
        for (int i = 0; i < MultiParts.size(); i++)
        {
            retValue = BaseSum(retValue, MultiParts.get(i), Base);
        }
        return retValue;
    }

    public static String BaseSum(String a, String b, String Base)
    {
        // this huge block is a tribute to java not having "Reverse()" method.
        char[] x = new char[a.length()];
        char[] y = new char[b.length()];
        for(int i = 0; i < a.length(); i++) {
            x[i] = a.charAt(a.length()-i);
        }
        for(int i = 0; i < b.length(); i++) {
            y[i] = a.charAt(a.length()-i);
        }
        a = new String(x);
        b = new String(y);
        // ---------------------------------------------------------------------
        String greater = a.length() > b.length() ? a : b;
        String lesser = a.length() < b.length() ? a : b;
        int leftOvers = 0;
        ArrayList<Character> result = new ArrayList();
        for (int i = 0; i < greater.length() || leftOvers > 0; i++)
        {
            int sum;
            if (i >= greater.length())
                sum = leftOvers;
            else if (i >= lesser.length())
                sum = leftOvers + Base.indexOf(greater.charAt(i));
            else
                sum = Base.indexOf(a.charAt(i)) + Base.indexOf(b.charAt(i)) + leftOvers;
            leftOvers = 0;
            if (sum > Base.length()-1)
            {
                while (sum > Base.length()-1)
                {
                    sum -= Base.length();
                    leftOvers += 1;
                }
                result.add(Base.charAt(sum));
            }
            else
            {
                result.add(Base.charAt(sum));
                leftOvers = 0;
            }
        }
        char[] reverseResult = new char[result.size()];
        for(int i = 0; i < result.size(); i++)
            reverseResult[i] = result.get(result.size() -i);
        return new String(reverseResult);
    }

    public static String BaseConvertItoA(long number, String base)
    {
        ArrayList<Character> retValue = new ArrayList<>();
        boolean negative = false;
        long backup = number;
        if (negative = (backup < 0))
            backup = -backup;
        do
        {
            int index = (int)(backup % base.length());
            retValue.add(base.charAt(index));
            backup = backup / base.length();
        } while ((backup) > 0);
        if (negative)
            retValue.add('-');
        char[] reverseRetVal = new char[retValue.size()];
        for(int i = 0; i < retValue.size(); i++)
            reverseRetVal[i] = retValue.get(retValue.size()-i);
        return new String(reverseRetVal);
    }

    public String ToString(String base)
    {
        if(base == null || base.length() < 2)
            base = "0123456789";
        ArrayList<Character> retVal = new ArrayList<>();
        char[] CharsBase = base.toCharArray();
        int TamanhoBase = base.length();
        String result = ""+base.charAt(0);
        String multi = ""+base.charAt(1);
        String lbase = IntEx.BaseConvertItoA(baseSize, base);
        for (int i = 0; i < digits.size(); i++)
        {
            String ThisByte = IntEx.BaseConvertItoA(digits.get(i), base);
            String Next = IntEx.BaseMult(ThisByte, multi, base);
            result = IntEx.BaseSum(result, Next, base);
            multi = IntEx.BaseMult(multi, lbase, base);
        }
        return result;
    }

    public static void main(String... args) {
        int ref = 0;
        IntEx result = new IntEx(0);
        while(++ref <= 1000)
        {
            IntEx mul = new IntEx(1000);
            for (int i = 0; i < 1000; ++i) {
                mul.multiply(new IntEx(i));
            }
            result.add(mul);
        }
        System.out.println(result.toString());
    }
}

Отказ от ответственности: это приблизительный перевод / локализация из исследования C #, в нем много опущенного кода. Это "почти" та же логика, что и java.math.BigInteger (вы можете открыть код BigInteger в своем любимом конструкторе и проверить себя. Если можно, я забываю перегруженный оператор, не переведенный на java, проявите немного терпения и прощения. , этот пример предназначен только для пояснения теории "возможно".

Кроме того, просто отступление, я знаю, что это «Пытаюсь изобрести велосипед», но, учитывая, что этот вопрос имеет академическую цель, я думаю, что его довольно разумно поделиться. Результат этого исследования можно увидеть на gitHub (хотя он не локализован), я не расширяю этот C # код здесь для его очень обширного, а не языка этого вопроса.

Это дает правильный ответ без лишних вычислений. Достаточно длинного.

public String lastTen() {
        long answer = 0;
        String txtAnswer = "";
        int length = 0;
        int i = 1;

        for(i = 1; i <= 1000; i++) {
            answer += Math.pow(i, i);
            txtAnswer = Long.toString(answer);
            length = txtAnswer.length();
            if(length > 9) break;
        }
        return txtAnswer.substring(length-10);
    }