注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ3122][Sdoi2013]随机数生成器  

2015-01-05 18:06:47|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3122: [Sdoi2013]随机数生成器

BZOJ太坑爹了……居然没写P保证是质数这么关键的条件……害的我蛋疼了半天
一道题边颓边写搞了一下午QAQ
13年的省选题……需要各种蛋疼的特判,所以一定要写个暴力拍一下
题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<map>
#include<algorithm>
using namespace std;
int n,m,P,C;
typedef long long ll;
int scan(){int i=0;scanf("%d",&i);return i;}
int kpow(int x,int k){
int re=1;
for(;k;k/=2,x=(ll)x*x%P)
if(k&1)re=(ll)re*x%P;
return re;
}
map<int,int>hash;
int mlog(int a,int C){
int sqn = sqrt(P)+1,i,j,tmp,inva,at;
hash.clear();
tmp = 1;
inva = kpow(a,P-2);
for(i=0;i<sqn;i++,tmp=(ll)tmp*inva%P)
if(!hash.count((j=(ll)C*tmp%P)))
hash[j] = i;
at = kpow(a,sqn);tmp = 1;j=0;
for(i=0;i<=sqn;i++,tmp=(ll)tmp*at%P)
if(hash.count(tmp))
return hash[tmp]+i*(sqn);
return -1;
}
int main(){
//freopen("in.txt","r",stdin);
int i,j,a,b,X1,Xn,ans;
int A,B;
int nn = scan();
while(nn--){
P = scan();
a = scan();b = scan();
X1 = scan();Xn = scan();
if(Xn == X1){printf("1\n");continue;}
if(a==0){
if(Xn == b)printf("2\n");
else printf("-1\n");
continue;
}
if(a==1){
ans = (ll)((Xn-X1)%P+b)*kpow(b,P-2)%P;
if(ans < 0)ans += P;
if(ans>0)printf("%d\n",ans);
else if(b==0)printf("%d\n",-1);
else printf("%d\n",P);
continue;
}
//a^n = a * (Xn(1-a)-b) * (X1*(1-a)-b)^(-1)
//a^n = a * B * A^(-1)
//A' = A^(-1)
//B' = a*B
//a^n = A'*B'
A = ((ll)X1*(1-a)-b)%P;
A = kpow(A,P-2);
B = ((ll)Xn*(1-a)-b)%P;
A = (ll)A*B%P;
//printf("%d\n",A);
//n = loga(A*B)
ans = mlog(a,A);
if(ans >= 0)ans++;
printf("%d\n",ans);
}
return 0;
}

题解:
Xn的式子展开之后用等比数列求和公式可以得到Xn的通项
然后移项就的得到了式子
a^(n-1) = (Xn(1-a)-b) * (X1*(1-a)-b)^(-1)
然后用离散对数求n就好了。
注意这里不要化成a^n = ....的形式,因为离散对数求的是最小解,而n != 0,如果n=0的话实际意义是n=P。
然后还有很多情况需要特判:
①a=0
②a=1,ans=0,b=0
②a=1,ans=0,b != 0
  评论这张
 
阅读(429)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017