题目大意就是求 a^x = b(mod c) 中的x

用一般的baby step giant step 算法会超时

这里参考的是http://hi.baidu.com/aekdycoin/item/236937318413c680c2cf29d4

map平衡树查找值

 #include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <map>
using namespace std;
#define ll long long int q_pow(int a , int b , int mod)
{
ll ans = ;
while(b)
{
if(b&) ans =((ll)ans*a)%mod;
a = ((ll)a*a)%mod;
b>>=;
}
return ans;
} int gcd(int a , int b)
{
if(b == )return a;
else return gcd(b,a%b);
} int ex_gcd(int a , int &x , int b , int &y)
{
if(b == ){
x= , y=;
return a;
}
int ans = ex_gcd(b , x , a%b , y);
int t = x;
x=y , y = t-a/b*y;
return ans;
} int inv(int a , int b , int mod)
{
int x , y , d;
d = ex_gcd(a , x , mod , y);
int e = (ll)x*b%mod;
return e<?e+mod:e;
} int BabyStep(int A,int B,int C){
map<int,int> Hash;
ll buf=%C,D=buf,K;
int i,d=,tmp;
for(i=;i<=;buf=buf*A%C,++i)
if(buf==B) return i;
while((tmp=gcd(A,C))!=)
{
if(B%tmp)return -;
++d;
C/=tmp;
B/=tmp;
D=D*A/tmp%C;
}
Hash.clear();
int M=(int)ceil(sqrt((double)C));
for(buf=%C,i=;i<=M;buf=buf*A%C,++i)
if(!Hash.count((int)buf))Hash[(int)buf]=i;
for(i=,K=q_pow((ll)A,M,C);i<=M;D=D*K%C,++i)
{
tmp=inv(D,B,C);
if(tmp>=&&Hash.count(tmp))return i*M+Hash[tmp]+d;
}
return -;
}
int main()
{
// freopen("a.in" ,"r" , stdin);
int k , p , n;
while(scanf("%d%d%d" , &k , &p , &n) == )
{
if(n>=p){
puts("Orz,I can’t find D!");
continue;
}
int ans = BabyStep(k , n , p);
if(ans == -) puts("Orz,I can’t find D!");
else printf("%d\n" , ans);
}
return ;
}

hash表查找值(效率高很多)hash是线性查找:

 #include<iostream>
#include<map>
#include<cmath>
#include <cstdio>
using namespace std;
typedef long long LL;
const int maxn = ;
struct hash{
int a,b,next;
}Hash[maxn << ];
int flg[maxn + ];
int top,idx;
//hash值插入
void ins(int a,int b){
int k = b & maxn;
if(flg[k] != idx){
flg[k] = idx;
Hash[k].next = -;
Hash[k].a = a;
Hash[k].b = b;
return ;
}
while(Hash[k].next != -){
if(Hash[k].b == b) return ;
k = Hash[k].next;
}
Hash[k].next = ++ top;
Hash[top].next = -;
Hash[top].a = a;
Hash[top].b = b;
}
//hash值查找
int find(int b){
int k = b & maxn;
if(flg[k] != idx) return -;
while(k != -){
if(Hash[k].b == b) return Hash[k].a;
k = Hash[k].next;
}
return -;
}
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}
int ext_gcd(int a,int b,int& x,int& y)
{
int t,ret;
if (!b){x=,y=;return a;}
ret=ext_gcd(b,a%b,x,y);
t=x,x=y,y=t-a/b*y;
return ret;
}
int Inval(int a,int b,int n){
int x,y,e;
ext_gcd(a,n,x,y);
e=(LL)x*b%n;
return e<?e+n:e;
}
int pow_mod(LL a,int b,int c)
{
LL ret=%c;
a%=c;
while(b){
if(b&)ret=ret*a%c;
a=a*a%c;
b>>=;
}
return ret;
}
int BabyStep(int A,int B,int C){
top = maxn; ++ idx;
LL buf=%C,D=buf,K;
int i,d=,tmp;
for(i=;i<=;buf=buf*A%C,++i)
if(buf==B)return i;
while((tmp=gcd(A,C))!=){
if(B%tmp)return -;
++d;
C/=tmp;
B/=tmp;
D=D*A/tmp%C;
}
int M=(int)ceil(sqrt(C+0.5));
for(buf=%C,i=;i<=M;buf=buf*A%C,++i)
ins(i,buf);
for(i=,K=pow_mod((LL)A,M,C);i<=M;D=D*K%C,++i){
tmp=Inval((int)D,B,C);
int w ;
if(tmp>=&&(w = find(tmp)) != -) return i*M+w+d;
}
return -;
}
int main(){
int A,B,C;
while(scanf("%d%d%d",&A,&C,&B)!=EOF){
if(B>C){
puts("Orz,I can’t find D!");
continue;
}
int tmp=BabyStep(A,B,C);
if(tmp<)
puts("Orz,I can’t find D!");
else printf("%d\n",tmp);
}
return ;
}

最新文章

  1. JQuery中对option的添加、删除、取值
  2. Windows Azure HandBook (6) Azure带宽与Azure Blob云存储
  3. PHP-----二维数组和二分查找
  4. 当在ECLIPSE中import现存项目时,如遇到版本不符
  5. Android服务之Service
  6. Linux使用小笔记&lt;安装篇&gt;
  7. webstorm激活破解码+++使用技巧
  8. Redis安装及使用详解
  9. loj 6008 餐巾计划 - 费用流
  10. SQL 数据库高CPU占用语句排查
  11. String.IsNullorEmpty()方法的使用
  12. laravel路由不生效,404,除了/ 都不行,关于nginx环境下laravel除了默认路由都出现404报错的处理方法
  13. Sublime text3配置xdebug调试记录
  14. 【vs2010】转换到 COFF 期间失败: 文件无效或损坏
  15. nginx学习 一.window下安装
  16. (转)Spring用代码来读取properties文件
  17. linux内核源代码、配置与编译
  18. dev_cpu_dead
  19. aspxpopupcontrol弹出在aspxpivotgrid的下方
  20. POJ2513Colored Sticks(欧拉通路)(字典树)(并查集)

热门文章

  1. CalService
  2. Oracle代码 规则 创建表 表空间 用户等
  3. Repeater 的使用
  4. C#连接数据库_使用读取配置文件的方式
  5. React 实践心得:react-redux 之 connect 方法详解
  6. nginx for windows 安装
  7. web.xml 加载顺序
  8. Java线程-线程的基本状态
  9. Objective - c Foundation 框架详解2
  10. QScrollArea不能显示滚动条