Как реализовать преобразование типа string в тип int в Java? Нужно ли это делать в рамках задачи?

Question

[PanchishinM]

Задача на программирование повышенной сложности. Даны целые числа n и m (1≤n≤10^18, 2≤m≤10^5), необходимо найти остаток от деления n-го числа Фибоначчи на m

Sample Input:
11527523930876953 26673
Sample Output:
10552
Memory Limit: 256 MB
Time Limit: 5 seconds

Мое решение

import java.util.Scanner;
class Main {
public static void main(String[] args) {

Scanner in1 = new Scanner(System.in);
Scanner in2 = new Scanner(System.in);
int n = in1.nextInt();
int m = in2.nextInt();

int[] f = new int[1000000];

f[0] = 0;
f[1] = 1;


int i = 2;
for(; i <= n; i++) {
f[i] = (f[i-1]) + (f[i-2]);

}
System.out.println(f[i-1]%m);
}
}

Feedback

Failed test #1. Run time error: Exception in thread "main" java.util.InputMismatchException: For input string: "11527523930876953" at java.util.Scanner.nextInt(Scanner.java:2166) at java.util.Scanner.nextInt(Scanner.java:2119) at Main.main(main.java:8)

Изучать программирование начал с Паскаля, теперь изучаю Java. Почему, собственно, вопрос не был решен поисковиком: я бы хотел разобраться досконально в верности/вопиющей неправильности моего решения.

Спасибо.

Answer 1

[Миша Кринкин]

1. docs.oracle.com/javase/7/docs/api/java/math/BigInt...
2. Что-то входные данные не сходятся с ограничениями указанными в условиях, вы точно задачу правильно привели?
3. Все вычисления стоит производить сразу по модулю m, так как числа Фибоначчи растут очень быстро, а скорость работы с длинной арифметикой, соответственно, падает.
4. Даже если вы поборитесь с длинными числами, ваше решение при таких больших значениях n просто не уложится во временной лимит, я полагаю, что предполагается решение использующее произведение матриц и быстрое возведение в степень.

Comments

[PanchishinM]

Прошу прощения. Условия исправил.

[Миша Кринкин]

@PanchishinM ну тогда, похоже, что число должно помещаться в long на Java, все остальные комментарии (кроме 1 и 2) остаются без изменений.

Answer 2

[Alex Chistyakov]

int int42 = java.lang.Integer.parseInt("42", 10);

Всю жизнь из строк int'ы делались так.
А про класс Scanner я узнал вот сегодня.

Answer 3

[anyd3v]

лучше используйте BigInteger

При расчете числа фибоначи вам не объязательно хранить их (int[] f = new int[1000000]) достаточно знать предидущее и на каждой итерации их перезатирать.