NC20362. [SDOI2013]随机数生成器
描述
小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 3 -1
C++(g++ 7.5.0) 解法, 执行用时: 379ms, 内存消耗: 2164K, 提交时间: 2023-04-04 18:02:56
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll T, p, a, b, x1, t, ans;
inline ll qpow(ll x, ll n, ll mod, ll res = 1LL) {
for ( ; n; n >>= 1, x = x * x % mod) !(n & 1) ?: res = res * x % mod;
return res;
}
map<ll, ll> bs;
inline ll bsgs(ll a, ll b, ll c) {
ll m = sqrt(c) + 1; bs.clear();
for (ll k = 0, t = b; k <= m; k ++, t = t * a % c) bs[t] = k;
for (ll x = 1, t = qpow(a, m, c), base = t; x <= m; x ++, t = t * base % c)
if (bs.count(t)) return ((x * m - bs[t]) % c + c) % c;
return -2;
}
signed main() {
scanf("%lld", &T);
while (T--) {
scanf("%lld%lld%lld%lld%lld", &p, &a, &b, &x1, &t);
if (t == x1) { puts("1"); continue; }
if (a == 0) { puts( b == t ? "2" : "-1" ); continue; }
if (a == 1) { printf("%lld\n", b == 0 ? -1 : qpow(b, p - 2, p) * ((t - x1) % p + p) % p + 1); continue; }
printf("%lld\n", bsgs(a, (t * (a - 1) + b) % p * qpow((x1 * (a - 1) + b) % p, p - 2, p) % p, p) + 1);
}
return 0;
}
C++ 解法, 执行用时: 198ms, 内存消耗: 2184K, 提交时间: 2021-08-03 10:19:23
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll T, p, a, b, x1, t, ans;
inline ll qpow(ll x, ll n, ll mod, ll res = 1LL) {
for ( ; n; n >>= 1, x = x * x % mod) !(n & 1) ?: res = res * x % mod;
return res;
}
map<ll, ll> bs;
inline ll bsgs(ll a, ll b, ll c) {
ll m = sqrt(c) + 1; bs.clear();
for (ll k = 0, t = b; k <= m; k ++, t = t * a % c) bs[t] = k;
for (ll x = 1, t = qpow(a, m, c), base = t; x <= m; x ++, t = t * base % c)
if (bs.count(t)) return ((x * m - bs[t]) % c + c) % c;
return -2;
}
signed main() {
scanf("%lld", &T);
while (T--) {
scanf("%lld%lld%lld%lld%lld", &p, &a, &b, &x1, &t);
if (t == x1) { puts("1"); continue; }
if (a == 0) { puts( b == t ? "2" : "-1" ); continue; }
if (a == 1) { printf("%lld\n", b == 0 ? -1 : qpow(b, p - 2, p) * ((t - x1) % p + p) % p + 1); continue; }
printf("%lld\n", bsgs(a, (t * (a - 1) + b) % p * qpow((x1 * (a - 1) + b) % p, p - 2, p) % p, p) + 1);
}
return 0;
}