A. Вандал в столовой

Codeforces

IDCF10077A

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Надя Пивко обычная студентка обычного института. Естественно, любимое место Нади Пивко в институте – это столовая. Сегодня она в очередной раз решила покушать рис, мясо по-французски (конечно, с подливой), пирожное и чай. Сев за стол, она увидела результат работы вандала! На столе было нацарапано: f1(n) = an - bn Отодвинув тарелку, Надя Пивко обнаружила ещё одну надпись: f2(n) = A * f2(n - 1) + B * f2(n - 2) Поскольку Надя Пивко пришла в столовую одна, то ей стало скучно, поэтому она решила разгадать, что же всё-таки хотел поведать вандал, надругавшись над столом. Поразмыслив немного, Надя Пивко решила, что последовательности могут быть одинаковы, но для этого необходимо задать А и В. Внезапно прозвенел звонок и ей пришлось убежать на мат. логику и задача осталась нерешённой. Помогите Наде Пивко найти А и В, а так же f2(0) и f2(1) при заданных а и b, причём полученная последовательность f2(n) должна быть идентична последовательности f1(n). В единственной строке даны целые числа a и b (1 ≤ a,b ≤ 109, a ≠ b). В единственной строке выведите четыре числа через пробел – f2(0) и f2(1), а затем полученные коэффициенты А и В. ## Входные Данные В единственной строке даны целые числа a и b (1 ≤ a,b ≤ 109, a ≠ b). ## Выходные Данные В единственной строке выведите четыре числа через пробел – f2(0) и f2(1), а затем полученные коэффициенты А и В. ## Примеры Входные данные3 2Выходные данные0 1 5 -6 [samples]

**Definitions** Let $ a, b \in \mathbb{Z} $, $ 1 \leq a, b \leq 10^9 $, $ a \neq b $. Define sequence $ f_1(n) = a^n - b^n $ for $ n \geq 0 $. Define sequence $ f_2(n) $ by the recurrence: $ f_2(n) = A \cdot f_2(n-1) + B \cdot f_2(n-2) $ for $ n \geq 2 $, with initial values $ f_2(0), f_2(1) $ to be determined. **Constraints** $ f_2(n) = f_1(n) $ for all $ n \geq 0 $. **Objective** Find $ f_2(0) $, $ f_2(1) $, $ A $, and $ B $ such that the recurrence holds and $ f_2(n) = a^n - b^n $ for all $ n \geq 0 $.

API Response (JSON)

{
  "problem": {
    "name": "A. Вандал в столовой",
    "description": {
      "content": "Надя Пивко обычная студентка обычного института. Естественно, любимое место Нади Пивко в институте – это столовая. Сегодня она в очередной раз решила покушать рис, мясо по-французски (конечно, с подли",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10077A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Надя Пивко обычная студентка обычного института. Естественно, любимое место Нади Пивко в институте – это столовая. Сегодня она в очередной раз решила покушать рис, мясо по-французски (конечно, с подли...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ a, b \\in \\mathbb{Z} $, $ 1 \\leq a, b \\leq 10^9 $, $ a \\neq b $.  \nDefine sequence $ f_1(n) = a^n - b^n $ for $ n \\geq 0 $.  \nDefine sequence $ f_2(n) $ by the recurrence:  \n$ f...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments