BZOJ 3122 随机数生成器

时间:2022-09-27 12:51:30

http://www.lydsy.com/JudgeOnline/problem.php?id=3122

题意:给出p,a,b,x1,t

已知xn=a*xn-1+b%p,求最小的n令xn=t

首先,若x1=t,则返回1

若a=0,则若b=t 返回2,否则无解

若a=1,则T=t-x1+p%p,可以列出方程

b*x+p*y==T % p

若a>=2,则根据等比数列和可得

xn=t=x1*a^(n-1)+b*(a^(n-1)-1)/(a-1) %p

由于p为质数,所以令c=inv[a-1]=(a-1)^(p-2)

x1*a^(n-1)+b*c*(a^(n-1))==b*c+t %p

(x1+b*c)*(a^(n-1))==b*c+t % p

令A=x1+b*c,B=p,C=b*c+t

则就是解A*X+B*Y==C %p

解出来X=a^(n-1),然后这个用BSGS求就可以了

 #include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<map>
#define ll long long
ll p;
ll read(){
char ch=getchar();ll t=,f=;
while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}
while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}
return t*f;
}
ll Pow(ll x,ll y){
ll res=;
if (x<) x=(x+p)%p;
while (y){
if (y%) res=(res*x)%p;
x=(x*x)%p;
y/=;
}
return res;
}
ll gcd(ll a,ll b){
if (b==) return a;
else return gcd(b,a%b);
}
void exgcd(ll a,ll b,ll &x,ll &y){
if (b==){
x=;
y=;
return;
}
exgcd(b,a%b,x,y);
ll T=x;
x=y;
y=T-(a/b)*y;
}
ll reverse(ll X){
ll A=X,B=p;
ll x,y;
exgcd(A,B,x,y);
return (x%p+p)%p;
}
ll work(ll a,ll b){
a%=p;
if (a==){
if (b==) return ;
else return -;
}
std::map<ll,int> mp;
ll m=sqrt(p)+,I=,Im=Pow(a,p--m),t=;
mp.clear();mp[]=m+;
for (int i=;i<m;i++){
t=t*a%p;
if (!mp[t]) mp[t]=i;
}
for (int k=;k<m;k++){
int i=mp[I*b%p];
if (i){
if (i==m+) i=;
return i+k*m;
}
I=I*Im%p;
}
return -;
}
ll solve(ll a,ll b,ll x1,ll t){
if (t==x1) {
return ;
}
if (a==){
if (b==t){
return ;
}
return -;
}
if (a==){
ll A=b,B=p,T=(t-x1+p)%p;
ll D=gcd(A,B);
if (T%D) {
return -;
}
T/=D;
ll x,y;
exgcd(A,B,x,y);
x=(x*T)%p;
while (x<) x+=p;
return x+;
}
ll c=Pow(a-,p-);
ll A=(b*c+x1)%p,B=p,T=(b*c+t)%p;
if (A<) A=(A+p)%p;
if (B<) B=(B+p)%p;
ll D=gcd(A,B);
if (T%D){
return -;
}
T/=D;
ll x,y;
exgcd(A,B,x,y);
while (x<) x=(x+p)%p;
x=(x*T)%p;
ll ans=work(a,x);
if (ans!=-) return ans+;
else return ans;
}
int main(){
int Tcase;
scanf("%d",&Tcase);
while (Tcase--){
ll a,b,x1,t;
p=read();a=read();b=read();x1=read();t=read();
printf("%lld\n",solve(a,b,x1,t));
}
}

BZOJ 3122 随机数生成器的更多相关文章

  1. bzoj 3122 随机数生成器 - BSGS

    Description Input 输入含有多组数据,第一行一个正整数T,表示这个测试点内的数据组数.   接下来T行,每行有五个整数p,a,b,X1,t,表示一组数据.保证X1和t都是合法的页码. ...

  2. &lbrack;BZOJ&rsqb;3671 随机数生成器&lpar;Noi2014&rpar;

    洛谷上卡不过去的朋友们可以来看看小C的程序(小C才不是标题党呢!) Description Input 第1行包含5个整数,依次为 x_0,a,b,c,d ,描述小H采用的随机数生成算法所需的随机种子 ...

  3. BZOJ 2875 随机数生成器

    http://www.lydsy.com/JudgeOnline/problem.php?id=2875 题意:给出mod,a,c,g,x0,n,xn=(a*xn-1+c)%mod,求xn%g 求A* ...

  4. bzoj 3671 随机数生成器 —— 暴力

    题目:https://www.lydsy.com/JudgeOnline/problem.php?id=3671 原来256M是可以开两个3e7的数组的: 因为答案只有 n+m-1 个数,所以暴力判断 ...

  5. 【BZOJ 3122】 &lbrack;Sdoi2013&rsqb;随机数生成器 &lpar;BSGS&rpar;

    3122: [Sdoi2013]随机数生成器 Time Limit: 10 Sec  Memory Limit: 256 MBSubmit: 1442  Solved: 552 Description ...

  6. BZOJ 3122 【SDOI2013】 随机数生成器

    题目链接:随机数生成器 经典数学题…… 为了方便接下来的处理,我们可以先把\(X_1=t\)的情况特判掉. 当\(a=0\)的时候显然只需再判一下\(b\)是否等于\(t\)即可. 当\(a=1\)的 ...

  7. 【BZOJ】【3671】【NOI2014】随机数生成器

    贪心 嗯……其实生成这个矩阵就是一个$O(n^2)$的模拟 = = 然后?字典序最小?贪心呗= =能选1就选1,然后能选2就选2…… 我们发现,对于矩阵(1,1)~(n,m),假设1的位置是(x,y) ...

  8. BZOJ 2875&colon; &lbrack;Noi2012&rsqb;随机数生成器&lpar; 矩阵快速幂 &rpar;

    矩阵快速幂...+快速乘就OK了 ----------------------------------------------------------------------------------- ...

  9. Bzoj 2875&colon; &lbrack;Noi2012&rsqb;随机数生成器&lpar;矩阵乘法&rpar;

    2875: [Noi2012]随机数生成器 Time Limit: 10 Sec Memory Limit: 512 MB Submit: 2052 Solved: 1118 Description ...

随机推荐

  1. Ubuntu菜鸟入门(四)—— 搜狗输入法

    一 搜狗输入法安装 1  下载安装包:   http://pinyin.sogou.com/linux/ 2  安装安装包 (1)"GDebi",这是一个用于安装你自己手动下载包的 ...

  2. Leveldb之version与version&lowbar;set详细对比

    version类包含的重要变量: VersionSet* vset_; // VersionSet to which this Version belongs Version* next_; // N ...

  3. nutch简介

    1.什么是 nutch Nutch 是一个开源的. Java 实现的搜索引擎.它提供了我们运行自己的搜 索引擎所需的全部工具.2.研究 nutch 的原因(1) 透明度: nutch 是开放源代码的, ...

  4. Update关联查询不走索引,效率低下

    优化一个sql,就是有A,B两个表,要利用b表的字段更新a表对应的字段.形如 Sql代码 update A set A.a=(select B.b from B where A.id=B.id); 原 ...

  5. Html中插入javascript不识别问题

    今天,在敲代码的时候往html中加入一个JavaScript代码段.如下所示,加入后var没有自动变颜色,起初以为没有大问题,于是就接着往下敲. 调试的时候,发现没有反应. <script la ...

  6. 【机器学习】主成分分析法 PCA (I)

    主成分分析算法是最常见的降维算法,在PCA中,我们要做的是找到一个方向向量,然后我们把所有的数都投影到该向量上,使得投影的误差尽可能的小.投影误差就是特征向量到投影向量之间所需要移动的距离. PCA的 ...

  7. VIVADO 入门之仿真与逻辑分析仪使用

    多路分频器设计 在第七节的学习中,笔者带大家通过一个入门必学的流水灯实验实现,快速掌握了VIVADO基于FPGA开发板的基本流程.考虑到很多初学者并没有掌握好Vivado 下FPGA的开发流程,本章开 ...

  8. CocosCreator的Sprite的更换

    先上图,左侧是运行的效果, cc.Class({ extends: cc.Component, /* * cocos creator动态更换纹理 *方法一,预先在编辑器里设置好所有的纹理,绑定到对应的 ...

  9. transaction注解分析

    1. Spring事务的基本原理 事务管理是应用系统开发中必不可少的一部分.Spring 为事务管理提供了丰富的功能支持.Spring 事务管理分为编码式和声明式的两种方式.编程式事务指的是通过编码方 ...

  10. PyTorch学习系列&lpar;九&rpar;——参数&lowbar;初始化

    from:http://blog.csdn.net/VictoriaW/article/details/72872036 之前我学习了神经网络中权值初始化的方法 那么如何在pytorch里实现呢. P ...