数学:拓展BSGS
2024-09-27 01:28:58
当C不是素数的时候,之前介绍的BSGS就行不通了,需要用到拓展BSGS算法
方法转自https://blog.csdn.net/zzkksunboy/article/details/73162229
典型例题是POJ3243
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
struct Hashmap
{
static const int Ha=,maxe=;
int E,lnk[Ha],son[maxe+],nxt[maxe+],w[maxe+];
int top,stk[maxe+];
void clear() {E=;while (top) lnk[stk[top--]]=;}
void Add(int x,int y) {son[++E]=y;nxt[E]=lnk[x];w[E]=0X7fffffff;lnk[x]=E;}
bool count(int y)
{
int x=y%Ha;
for (int j=lnk[x];j;j=nxt[j])
if (y==son[j]) return true;
return false;
}
int& operator [] (int y)
{
int x=y%Ha;
for (int j=lnk[x];j;j=nxt[j])
if (y==son[j]) return w[j];
Add(x,y);stk[++top]=x;return w[E];
}
}f;
int gcd(int a,int b)
{
return b==?a:gcd(b,a%b);
}
int exgcd(int a,int b,int &x,int &y)
{
if(b==) {x=;y=;return a;}
int r=exgcd(b,a%b,x,y);
int t=x;x=y;y=t-a/b*y;
return r;
}
int exBSGS(int A,int B,int C)
{
if(C==) if(B==) return A!=; else return -;
if(B==) if(A!=) return ; else return -;
if(A%C==) if(B==) return ; else return -;
int r,D=,num=;
while((r=gcd(A,C))>)
{
if(B%r) return -;
num++;
B/=r;C/=r;D=((long long)D*A/r)%C;
}
for(int i=,tmp=;i<num;i++,tmp=((long long)tmp*A)%C)
if(tmp==B) return i;
int m=ceil(sqrt(C)),Base=;f.clear();
for(int i=;i<=m-;i++)
{
f[Base]=min(f[Base],i);
Base=((long long)Base*A)%C;
}
for(int i=;i<=m-;i++)
{
int x,y,r=exgcd(D,C,x,y);
x=((long long)x*B%C+C)%C;
if(f.count(x)) return i*m+f[x]+num;
D=((long long)D*Base)%C;
}
return -;
}
int main()
{
int A,B,C;
while(scanf("%d%d%d",&A,&C,&B)==)
{
if(!A&&!B&&!C) break;
int ans=exBSGS(A,B,C);
if(ans==-) printf("No Solution\n");
else printf("%d\n",ans);
}
return ;
}
给哈希好评,哪天好好整理一下
最新文章
- springmvc+mybatis事务回滚
- 【四】搭建Markdown的编辑器
- UITextFeild的用法
- Config文件
- java实现文件及目录压缩
- Mahout源码分析之 -- 文档向量化TF-IDF
- 李洪强iOS开发之OC[013] -类的创建的练习
- 如何测试 Android 中的定时事件
- Linux内核中SPI/I2c子系统剖析
- sublime text3中的常用插件
- 5步做一个 TensorFlow 聊天机器人:DeepQA
- Leetcode解题-树(5.0.0)基础类
- Cocos2D:塔防游戏制作之旅(三)
- qmake: could not exec &#39;/usr/lib/x86_64-linux-gnu/qt4/bin/qmake&#39;: No such file or directory
- 一些常用的js循环,如for
- ES6 扩展运算符 三点(...)
- 12C -- ORA-65048 ORA-65048
- iOS - 切换rootViewController时,销毁之前的控制器
- bzoj4448 情报传递
- Android Studio 3.0.1 版本包下载
热门文章
- 官方文档 恢复备份指南二 Getting Started with RMAN
- POJ 2653 Pick-up sticks(线段判交)
- Python—列表(一个“打了激素”的数组)
- LintCode-211.字符串置换
- 软工网络15团队作业——Alpha阶段敏捷冲刺 DAY1
- week1 四人小组项目
- 【Linux】- CentOS安装Mysql 5.7
- MVC绕过登陆界面验证时HttpContext.Current.User.Identity.Name取值为空问题解决方法
- javascript标准对象与包装对象
- 以安装PyTorch为例说明Anaconda在Windows/Linux上的使用