Space Voyage

题意翻译

## 题目描述 来自ABBYY星球的智能海狸计划在一艘超现代宇宙飞船上进行太空旅行。在航行期间，他计划访问 $n$ 个行星。对于行星 $i$ ， $a_{i}$ 是外星游客被允许带到该星球的最大行李箱数量， $b_{i}$ 是该星球上的公民人数。 聪明的海狸将把ABBYY上的一些礼物带到他将要访问的行星上。礼物装在行李箱里，每个行李箱中 $x$ 个。海狸将带到船上恰好 $a_{1}+\dots+a_{n}$ 个手提箱。 当海狸降落在第 $i$ 个星球，他将带着 $a_{i}$ 个手提箱出门。在该星球上的第一天，海狸会去散步以了解公民。在第二天和随后的所有日子里，海狸都会向公民赠送礼物，使得每个公民每天获得一份礼物。海狸在第一个满足留下的礼物数量严格少于公民数量那个晚上离开。换句话说，如果一天晚上他发现留下的礼物数量不足以让他第二天给每个公民一份礼物的那个晚上离开。他会把剩下的礼物留在酒店。 海狸想知道，他可以选择几个 $x$ ，使得他将花费恰好 $c$ 天旅行。（在行星之间的飞行中花费的时间被认为是零） ## 输入格式 第一行输入包含空格分隔的整数 $n$ 和 $c$ ——海狸将要访问的行星 数量以及他将花费旅行的天数。下 $n$ 行每行包含一对以空格分隔的整数$a_{i},b_{i}$ $(1\le i\le n）$ —— 他最多可以携带的行李箱数量以及该星球上的公民人数 ## 输出格式 打印单个数字 $k$ —— 选择方式的数量。如果 $x$ 有无限多个可能的值，请打印`-1`。 ## 输入输出样例 **输入 $#1$** ``` 2 5 1 5 2 4 ``` **输出 #1** ``` 1 ``` ## 说明/提示 #### 样例解释 在第一个示例中，只有一个合适的值（$x=5$）。海狸先带着1个手提箱和5个礼物去第一个星球。在这里，他花了2天时间：第一天他闲逛，第二天送出五件礼物。他接着带着2个手提箱和10件礼物来到第二个星球。在这里，他花了3天 - 他在第二天和第三天送出4份礼物，并将剩余的2份礼物留在酒店。海狸总共花了5天时间旅行。如果 $x=4$ 或者更少,海狸在第一颗行星上的第二天没有足够的礼物，所以航行会结束得太快。如果 $x=6$ 或更多，的海狸将在第二颗行星上至少再呆一天，航行将花费太长时间。 #### 部分分 - 对于 $30\%$ 的数据，$1\le n\le 100$，$1\le a_{i},b_{i},c \le 100$ - 对于 $100\%$ 的数据，$1\le n\le 10^{4}$，$1\le a_{i},b_{i},c \le 10^{9}$ #### 温馨提示 由于 32 位整数可能会溢出，建议使用 64 位算术。在某些解决方案中，甚至 64 位算术也可能溢出。所以在计算时要小心！另外，在`C++`中,请不要使用 `%lld` 说明符读取或写入 64 位整数。最好使用 `cin`、`cout` 流或 `%I64d` 说明符。 感谢@[我不是管理员](/user/398726)提供翻译

题目描述

The Smart Beaver from ABBYY plans a space travel on an ultramodern spaceship. During the voyage he plans to visit $ n $ planets. For planet $ i $ $ a_{i} $ is the maximum number of suitcases that an alien tourist is allowed to bring to the planet, and $ b_{i} $ is the number of citizens on the planet. The Smart Beaver is going to bring some presents from ABBYY to the planets he will be visiting. The presents are packed in suitcases, $ x $ presents in each. The Beaver will take to the ship exactly $ a_{1}+...+a_{n} $ suitcases. As the Beaver lands on the $ i $ -th planet, he takes $ a_{i} $ suitcases and goes out. On the first day on the planet the Beaver takes a walk and gets to know the citizens. On the second and all subsequent days the Beaver gives presents to the citizens — each of the $ b_{i} $ citizens gets one present per day. The Beaver leaves the planet in the evening of the day when the number of presents left is strictly less than the number of citizens (i.e. as soon as he won't be able to give away the proper number of presents the next day). He leaves the remaining presents at the hotel. The Beaver is going to spend exactly $ c $ days traveling. The time spent on flights between the planets is considered to be zero. In how many ways can one choose the positive integer $ x $ so that the planned voyage will take exactly $ c $ days?

输入输出格式

输入格式

The first input line contains space-separated integers $ n $ and $ c $ — the number of planets that the Beaver is going to visit and the number of days he is going to spend traveling, correspondingly. The next $ n $ lines contain pairs of space-separated integers $ a_{i},b_{i} $ ( $ 1<=i<=n $ ) — the number of suitcases he can bring to the $ i $ -th planet and the number of citizens of the $ i $ -th planet, correspondingly. The input limitations for getting 30 points are: - $ 1<=n<=100 $ - $ 1<=a_{i}<=100 $ - $ 1<=b_{i}<=100 $ - $ 1<=c<=100 $ The input limitations for getting 100 points are: - $ 1<=n<=10^{4} $ - $ 0<=a_{i}<=10^{9} $ - $ 1<=b_{i}<=10^{9} $ - $ 1<=c<=10^{9} $ Due to possible overflow, it is recommended to use the 64-bit arithmetic. In some solutions even the 64-bit arithmetic can overflow. So be careful in calculations!

输出格式

Print a single number $ k $ — the number of ways to choose $ x $ so as to travel for exactly $ c $ days. If there are infinitely many possible values of $ x $ , print -1. Please do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specifier.

输入输出样例

输入样例 #1

2 5
1 5
2 4

输出样例 #1

1

说明

In the first example there is only one suitable value $ x=5 $ . Then the Beaver takes 1 suitcase with 5 presents to the first planet. Here he spends 2 days: he hangs around on the first day, and he gives away five presents on the second day. He takes 2 suitcases with 10 presents to the second planet. Here he spends 3 days — he gives away 4 presents on the second and the third days and leaves the remaining 2 presents at the hotel. In total, the Beaver spends 5 days traveling. For $ x=4 $ or less the Beaver won't have enough presents for the second day on the first planet, so the voyage will end too soon. For $ x=6 $ and more the Beaver will spend at least one more day on the second planet, and the voyage will take too long.