P3306 [SDOI2013]随机数生成器

    • 446通过
    • 2.1K提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 最大公约数,gcd 素数判断,质数,筛法 逆元 2013 山东 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    小W喜欢读书,尤其喜欢读《约翰克里斯朵夫》。最近小W准备读一本新书,这本书一共有$P$页,页码范围为$0 \cdots P-1$。

    小W很忙,所以每天只能读一页书。为了使事情有趣一些,他打算使用NOI2012上学习的线性同余法生成一个序列,来决定每天具体读哪一页。

    我们用Xi来表示通过这种方法生成出来的第$i$个数,也即小$W$第$i$天会读哪一页。这个方法需要设置$3$个参数$a,b,X1$,满足$0\leq a,b,X1\leq p-1$,且$a,b,X1$都是整数。按照下面的公式生成出来一系列的整数:$X_{i+1} \equiv aX_i+b \pmod p$其中$mod$表示取余操作。

    但是这种方法可能导致某两天读的页码一样。

    小W要读这本书的第$t$页,所以他想知道最早在哪一天能读到第t页,或者指出他永远不会读到第$t$页。

    输入输出格式

    输入格式:

    输入含有多组数据,第一行一个正整数$T$,表示这个测试点内的数据组数。

    接下来T行,每行有五个整数$p$,$a$,$b$,$X1$,$t$,表示一组数据。保证$X1$和$t$都是合法的页码。 注意:$P$一定为质数

    输出格式:

    共$T$行,每行一个整数表示他最早读到第$t$页是哪一天。如果他永远不会读到第$t$页,输出$-1$。

    输入输出样例

    输入样例#1: 复制
    3
    7  1 1 3 3
    7  2 2 2 0
    7  2 2 2 1
    输出样例#1: 复制
    1 
    3 
    -1

    说明

    $0\leq a\leq P-1,0\leq b\leq P-1,2\leq P\leq 10^9$

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。