P3306 [SDOI2013]随机数生成器

    • 73通过
    • 394提交
  • 题目提供者洛谷OnlineJudge
  • 标签 最大公约数,gcd 素数判断,质数,筛法 逆元 2013 山东 高性能
  • 难度 省选/NOI-
  • 时空限制 1s / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 推荐的相关题目

    题目描述

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

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

    我们用Xi来表示通过这种方法生成出来的第i个数,也即小W第i天会读哪一页。这个方法需要设置3个参数a,b,X1,满足0<=a,b,X1<=p-1,且a,b,X1都是整数。按照下面的公式生成出来一系列的整数:Xi+1=(aXi+b) mod 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<=a<=P-1,0<=b<=P-1,2<=P<=10^9

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