A5952 | 「WC2021」斐波那契
时间限制1s
内存限制512MB
通过 / 提交0/0
题目描述
众所周知，小葱同学擅长计算，尤其擅长计算组合数。但是对组合数有了充分研究的小葱同学对组合数失去了兴趣，而开始研究数列。
我们定义 $F_0 = a$，$F_1 = b$，$F_i = (F_{i-1} + F_{i-2}) \bmod m$（$i \ge 2$）。
现在给定 $n$ 组询问，对于每组询问请找到一个最小的整数 $p$，使得 $F_p = 0$。
我们定义 $F_0 = a$，$F_1 = b$，$F_i = (F_{i-1} + F_{i-2}) \bmod m$（$i \ge 2$）。
现在给定 $n$ 组询问，对于每组询问请找到一个最小的整数 $p$，使得 $F_p = 0$。
输入格式
第一行两个整数 $n, m$，代表询问的组数和每组计算中的模数。
接下来 $n$ 行每行两个整数 $a, b$，代表一组询问中 $F_0$ 和 $F_1$ 的值。
接下来 $n$ 行每行两个整数 $a, b$，代表一组询问中 $F_0$ 和 $F_1$ 的值。
输出格式
对于每组询问，输出一行一个整数 $p$ 代表答案。如果这样的 $p$ 不存在，输出
-1。输入输出样例
输入 #1
4 5 0 1 1 2 2 3 3 4
输出 #1
0 3 2 -1
输入 #2
1 6 4 4
输出 #2
3
对于所有测试点：$1 \le n, m \le {10}^5$，$0 \le a, b < m$。
每个测试点的具体限制见下表：
| 测试点编号 | $n, m \le$ | 特殊限制 |
|:-:|:-:|:-:|
| $1 \sim 2$ | $1000$ | 无 |
| $3 \sim 4$ | ${10}^5$ | $m$ 是质数 |
| $5 \sim 6$ | ${10}^5$ | $m = p_1 p_2 \cdots p_k$，其中 $p_i$ 是两两不同的质数 |
| $7 \sim 10$ | ${10}^5$ | 无 |
每个测试点的具体限制见下表：
| 测试点编号 | $n, m \le$ | 特殊限制 |
|:-:|:-:|:-:|
| $1 \sim 2$ | $1000$ | 无 |
| $3 \sim 4$ | ${10}^5$ | $m$ 是质数 |
| $5 \sim 6$ | ${10}^5$ | $m = p_1 p_2 \cdots p_k$，其中 $p_i$ 是两两不同的质数 |
| $7 \sim 10$ | ${10}^5$ | 无 |
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？