BZOJ3122 [SDOI2013] 随机数生成器

传送门

已知 a,b,X1,p,ta,b,X_1,p,t

给定递推公式 ,求最小的正整数i满足 Xi=tX_i=t ,p为质数。

题解

这道题需要分类讨论:

  1. X1=tX_1=t时,答案为1.
  2. 当a=0时,如果b=t,则答案为2,否则无解。
  3. 当a=1时,原题化为X1+ibtX_1+ib\equiv t,求最小正整数解,也就是ibtx1ib\equiv t-x_1

当a>1,显然

,所以

BSGS即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
/*
Author: CNYALI_LK
LANG: C++
PROG: 3122.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#include<tr1/unordered_map>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
using namespace std;
const double eps=1e-8;
const double PI=acos(-1.0);
typedef long long ll;
template<class T>ll chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>ll chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
ll p,a,b,x1,t;
ll fpm(ll a,ll b){
ll c=1;
while(b){
if(b&1)c=c*a%p;
a=a*a%p;
b>>=1;
}
return c;

}
ll inv(ll a){
ll b=p-2,c=1;
while(b){
if(b&1)c=c*a%p;
a=a*a%p;
b>>=1;
}
return c;
}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll BSGS(ll a,ll b){
if(b==1)return 1;
ll m=ceil(sqrt(p));
tr1::unordered_map<ll,ll> mp;
for(ll i=1;i<=m;++i){
b=b*a%p;
mp.insert(make_pair(b,i));
}
b=1;
a=fpm(a,m);
for(ll i=1;i<=m;++i){
b=b*a%p;
if(mp.count(b))return i*m-mp[b]+1;
}
return -1;
}
int main(){
#ifdef cnyali_lk
freopen("3122.in","r",stdin);
freopen("3122.out","w",stdout);
#endif
ll T;
scanf("%lld",&T);
while(T){
--T;
scanf("%lld%lld%lld%lld%lld",&p,&a,&b,&x1,&t);
if(x1==t)printf("1\n");
else
if(a==0){
if(b==t)printf("2\n");
else printf("-1\n");
}
else if(a==1){
if(!b)printf("-1\n");
else{
t=(t-x1+p)%p;
printf("%lld\n",1+t*inv(b)%p);
}
}
else{
b=(b+t*(a-1)%p)*inv(b+x1*(a-1)%p)%p;
printf("%lld\n",BSGS(a,b));
}
}
return 0;
}

文章目录
  1. 1. 题解
|

博客使用Disqus作为评论系统