306875: CF1264F. Beautiful Fibonacci Problem

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Beautiful Fibonacci Problem

题意翻译

现在给你一个长度为 $n$ 的递增的等差正整数数列 $(a,a+d,a+2d\dots a+(n-1)d)$。 需要你构造一个长度为 $n$ 的递增的等差正整数数列 $(b,b+e,b+2e\dots b+(n-1)e)$ 满足以下条件: + $0<b,e< 2^{64}$ + 对于所有的 $0\leq i <n$,$a+id$ 的十进制表示是 $F_{b+ie}$ 的十进制表示的后 $18$ 位的子串。(如果 $F_{b+ie}$ 没有 $18$ 位,那么考虑它的所有位) 其中 $F_i$ 是指斐波那契数列的第 $i$ 项($F_0=0,F_1=1$)。

题目描述

The well-known Fibonacci sequence $ F_0, F_1, F_2,\ldots $ is defined as follows: - $ F_0 = 0, F_1 = 1 $ . - For each $ i \geq 2 $ : $ F_i = F_{i - 1} + F_{i - 2} $ . Given an increasing arithmetic sequence of positive integers with $ n $ elements: $ (a, a + d, a + 2\cdot d,\ldots, a + (n - 1)\cdot d) $ . You need to find another increasing arithmetic sequence of positive integers with $ n $ elements $ (b, b + e, b + 2\cdot e,\ldots, b + (n - 1)\cdot e) $ such that: - $ 0 < b, e < 2^{64} $ , - for all $ 0\leq i < n $ , the decimal representation of $ a + i \cdot d $ appears as substring in the last $ 18 $ digits of the decimal representation of $ F_{b + i \cdot e} $ (if this number has less than $ 18 $ digits, then we consider all its digits).

输入输出格式

输入格式


The first line contains three positive integers $ n $ , $ a $ , $ d $ ( $ 1 \leq n, a, d, a + (n - 1) \cdot d < 10^6 $ ).

输出格式


If no such arithmetic sequence exists, print $ -1 $ . Otherwise, print two integers $ b $ and $ e $ , separated by space in a single line ( $ 0 < b, e < 2^{64} $ ). If there are many answers, you can output any of them.

输入输出样例

输入样例 #1

3 1 1

输出样例 #1

2 1

输入样例 #2

5 1 2

输出样例 #2

19 5

说明

In the first test case, we can choose $ (b, e) = (2, 1) $ , because $ F_2 = 1, F_3 = 2, F_4 = 3 $ . In the second test case, we can choose $ (b, e) = (19, 5) $ because: - $ F_{19} = 4181 $ contains $ 1 $ ; - $ F_{24} = 46368 $ contains $ 3 $ ; - $ F_{29} = 514229 $ contains $ 5 $ ; - $ F_{34} = 5702887 $ contains $ 7 $ ; - $ F_{39} = 63245986 $ contains $ 9 $ .

Input

题意翻译

现在给你一个长度为 $n$ 的递增的等差正整数数列 $(a,a+d,a+2d\dots a+(n-1)d)$。 需要你构造一个长度为 $n$ 的递增的等差正整数数列 $(b,b+e,b+2e\dots b+(n-1)e)$ 满足以下条件: + $0<b,e< 2^{64}$ + 对于所有的 $0\leq i <n$,$a+id$ 的十进制表示是 $F_{b+ie}$ 的十进制表示的后 $18$ 位的子串。(如果 $F_{b+ie}$ 没有 $18$ 位,那么考虑它的所有位) 其中 $F_i$ 是指斐波那契数列的第 $i$ 项($F_0=0,F_1=1$)。

加入题单

上一题 下一题 算法标签: