Biến Đổi Cặp Số

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Bessie likes cooking and wants to prepare a meal. She has a number of recipes and wants to pick one to use. However, she has a difficult time deciding between recipes, and she will cook the meal from the recipe that is chosen by a fair game.

This game involves a list of $n$ pairs of integers. Each pair of integers $(a_{i}, b_{i})$ has some information written on it. In each step of the game, Bessie picks a pair and performs one of two operations on it:

Operation A: $(a, b) \to (b, a + b)$
Operation B: $(a, b) \to (a + b, b)$

The game continues until all pairs are of the form $(F_{k}, F_{k + 1})$ for some integer $k \geq 1$ , where $F_{i}$ is the $i$ -th Fibonacci number.

How many pairs can Bessie modify?

Dữ liệu vào

Dòng đầu tiên chứa $n$ ( $1 \leq n \leq 10^{5}$ ), số lượng cặp.

$n$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a_{i}$ và $b_{i}$ ( $1 \leq a_{i}, b_{i} \leq 10^{9}$ ).

Dữ liệu ra

In ra số lượng cặp mà Bessie có thể biến đổi thành dạng $(F_{k}, F_{k + 1})$ .

Ràng buộc

$1 \leq n \leq 10^{5}$ $1 \leq a_{i}, b_{i} \leq 10^{9}$

Ví dụ

Input	Output	Giải thích
`2` `1 1` `3 5`	`2`	Cả hai cặp đều là Fibonacci
`3` `1 2` `5 8` `2 2`	`2`	Chỉ hai cặp (1,2) và (5,8) là Fibonacci

Bình luận

Không có bình luận tại thời điểm này.