A6429 | 「CodePlus 2017 12 月赛」可做题2
时间限制1s
内存限制512MB
通过 / 提交0/0
题目描述
“CodePlus 比赛的时候在做什么？有没有空？能来解决丢番图方程问题吗？”sublinekelzrip 这样问 qmqmqm。
当然，qmqmqm 并不会丢番图方程问题，所以 sublinekelzrip 改为提出了另一个题目，现在请你帮助 qmqmqm 解决这个题目。
<hr>
这个问题是这样的：
若一个数列 $a$ 满足条件 $a_n=a_{n-1}+a_{n-2},n \geq 3$，而 $a_1,a_2$ 为任意实数，则我们称这个数列为广义斐波那契数列。
现在请你求出满足条件 $a_1=i$，$a_2$ 为区间 $[l,r]$ 中的整数，且 $a_k \bmod p=m$ 的广义斐波那契数列有多少个。
当然，qmqmqm 并不会丢番图方程问题，所以 sublinekelzrip 改为提出了另一个题目，现在请你帮助 qmqmqm 解决这个题目。
<hr>
这个问题是这样的：
若一个数列 $a$ 满足条件 $a_n=a_{n-1}+a_{n-2},n \geq 3$，而 $a_1,a_2$ 为任意实数，则我们称这个数列为广义斐波那契数列。
现在请你求出满足条件 $a_1=i$，$a_2$ 为区间 $[l,r]$ 中的整数，且 $a_k \bmod p=m$ 的广义斐波那契数列有多少个。
输入格式
本题包含多组数据，输入第一行包含一个正整数 $T$，表示数据组数。对于每组数据：
一行六个用空格隔开的整数 $i,l,r,k,p,m$，意义如「题目描述」所示。
一行六个用空格隔开的整数 $i,l,r,k,p,m$，意义如「题目描述」所示。
输出格式
输出共 $T$ 行，每行一个数表示该组数据的答案。
输入输出样例
输入 #1
6 2 17 68 3 23 1 1 17 68 3 57 1 5 17 68 10 11 9 5 17 68 10 71 9 10 17 68 11 12 3 10 17 68 8 6 4
输出 #1
3 1 4 1 5 9
| 测试点 | $k$ | $r$ | 其他 |
|-|-|-|-|
| 1 | $\leq 100$ | $\leq 100$ | 无 |
| 2 | $\leq 10^5$ | $\leq 10^5$ | 无 |
| 3 | $\leq 10^5$ | $\leq 10^5$ | 无 |
| 4 | $\leq 10^{18}$ | $\leq 10^5$ | 无 |
| 5 | $\leq 10^{18}$ | $\leq 10^5$ | 无 |
| 6 | $\leq 10^5$ | $\leq 10^{18}$ | $p$为质数 |
| 7 | $\leq 10^5$ | $\leq 10^{18}$ | $p$为质数 |
| 8 | $\leq 10^{18}$ | $\leq 10^{18}$ | $p$为质数 |
| 9 | $\leq 10^{18}$ | $\leq 10^{18}$ | 无 |
| 10 | $\leq 10^{18}$ | $\leq 10^{18}$ | 无 |
对于所有数据，$0 \leq l \leq r$,$1 \leq p \leq 10^9$,$0 \leq m < p$,$T=10$,$0 \leq i \leq 10^{18}$,$k \geq 3$。
来自 CodePlus 2017 12 月赛，清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。 Credit：idea/卢政荣 命题/卢政荣 验题/吕时清，茹逸中，王聿中 Git Repo：https://git.thusaac.org/publish/CodePlus201712
感谢腾讯公司对此次比赛的支持。
来自 CodePlus 2017 12 月赛，清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。 Credit：idea/卢政荣 命题/卢政荣 验题/吕时清，茹逸中，王聿中 Git Repo：
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？