Номера слишком большие для переменных

Question

Я должен найти последние десять цифр 1^1 + 2^2 + 3^3 .. + 1000^1000. Есть ли способ найти это с чистой логикой? Я думаю, вы не можете сохранить номер, который большой.

Этот вопрос связан с математическим соревнованием, но я думал о попытке сделать это на Java.

Answer 1

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

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

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

---

Edit: В то время как вы не должны использовать 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.

Answer 2

Вы можете использовать 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); 
} 

Answer 3

Она может быть решена без 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.

Answer 4

использование 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); 
    } 
} 

Answer 5

Десятичная база использует 0 ... 9 (10 цифр), чтобы представить цифры, число, которое во втором положении справа налево представляет Цифры * 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 = ""; 
     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# здесь для его очень обширного, а не языка этого вопроса.

Answer 6

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

поднять^п, найти двоичное разложение п:

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) space (см. Ниже).

Далее, как вызов для того, чтобы избежать использования BigInteger, мы можем разбить вычисление на две части: найти ответ mod 2^10 и найти ответ mod 5^10. В обоих случаях числа в соответствующих диапазонах и продуктах чисел в соответствующих диапазонах соответствуют long с. Недостатком является то, что мы должны использовать китайскую теорему останова для рекомбинирования результатов, но это не так сложно, и это поучительно. Самая трудная часть использования китайской теоремы останова - поиск инверсий 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); 
    } 

} 

Answer 7

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

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); 
    }