#PQJ209x4124. QOJ 209_4124
QOJ 209_4124
全国青少年信息学奥林匹克
山东省省队选拔赛2013 第一轮 第一试 随机数生成器 随机数生成器 【问题描述】 小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 p 表示前面的数除以p 的余数。 可以发现,这个序列中下一个数总是由上一个数生成的,而且每一项都在 0..p-1 这个范围内,是一个合法的页码。同时需要注意,这种方法有可能导致某 两天读的页码完全一样。 小W 非常急切地想去读这本书的第t 页。所以他想知道,对于一组给定的a, b,X1,如果使用线性同余法来生成每一天读的页码,最早读到第t 页是在哪一 天,或者指出他永远不会读到第t 页。 【输入格式】 输入含有多组数据,第一行一个正整数T,表示这个测试点内的数据组数。 接下来T 行,每行有五个整数p,a,b,X1,t,表示一组数据。保证X1 和 t 都是合法的页码。 【输出格式】 共T 行,每行一个整数表示他最早读到第t 页是哪一天。如果他永远不会读 到第t 页,输出-1。 【样例输入】 3 7 1 1 3 3 7 2 2 2 0 7 2 2 2 1 【样例输出】 1 3 -1
全国青少年信息学奥林匹克
山东省省队选拔赛2013 第一轮 第一试 随机数生成器 【样例说明】
对于第一组数据,生成的序列为:3,4,5,6,0… 对于第二、三组数据,生成的序列为:2,6,0,2… 【数据规模和约定】 测试点编号 a b p 1 0≤a≤p-1 0≤b≤p-1 2≤p≤100 2 3 a=1 2≤p≤109 4 5 6 0≤a≤p-1 b=0 7 8 9 0≤b≤p-1 10
对于100%的测试数据:保证p 是质数,T≤50。