ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1133. Последовательность Фибоначчи

AC Java 1.8 0.078s 388 KB (top solution, 10th place)
Послано esbybb 6 авг 2015 10:52
//package timus;

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.Reader;
import java.math.BigInteger;
import java.util.StringTokenizer;

public class p1133 {

    public static void main(String[] args) throws FileNotFoundException {
        InputStream is = System.in;
//        is = new FileInputStream(new File("A.txt"));
        FastScanner sc = new FastScanner(new InputStreamReader(is));
        int i = sc.nextInt();
        int Fi = sc.nextInt();
        int j = sc.nextInt();
        int Fj = sc.nextInt();
        int n = sc.nextInt();
        if (i>j) {
            int reg = i; i = j; j = reg;
            reg = Fi; Fi = Fj; Fj = reg;
        }
        BigInteger f1 = fastFibonacciDoubling(j-i-1);
        BigInteger f2 = fastFibonacciDoubling(j-i);
        BigInteger pr = BigInteger.valueOf(Fj);
        BigInteger FI = BigInteger.valueOf(Fi);
        pr = pr.subtract(f2.multiply(FI));
        pr = pr.divide(f1);
        int diff = 0;
        if (n>i) {
            diff = n - i;
        } else {
            diff = i - n;
        }
        BigInteger a = fastFibonacciDoubling(diff).multiply(FI);
        BigInteger b = fastFibonacciDoubling(diff-1).multiply(pr);
        System.out.println(a.add(b));
    }

    private static BigInteger fastFibonacciDoubling(int n) {
        n++;
        BigInteger a = BigInteger.ZERO;
        BigInteger b = BigInteger.ONE;
        int m = 0;
        for (int i = 31 - Integer.numberOfLeadingZeros(n); i >= 0; i--) {
            BigInteger d = multiply(a, b.shiftLeft(1).subtract(a));
            BigInteger e = multiply(a, a).add(multiply(b, b));
            a = d;
            b = e;
            m *= 2;
            if (((n >>> i) & 1) != 0) {
                BigInteger c = a.add(b);
                a = b;
                b = c;
                m++;
            }
        }
        return a;
    }
    private static BigInteger multiply(BigInteger x, BigInteger y) {
        return x.multiply(y);
    }

    static class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        FastScanner(Reader in) {
            br = new BufferedReader(in);
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }

}