离散对数和BSGS算法

　　设$x$是最小的非负整数使得$a^{x}\equiv b\ \ \ \pmod{m}$，则$x$是$b$以$a$为底的离散对数，记为$x = ind_{a}b$。

　　假如给定$a, b, m$，考虑如何求$x$，或者输出无解，先考虑$(a, m) = 1$的情况。

定理1（欧拉定理） 若$(a, m) = 1$，则$a^{\varphi(m)}\equiv 1 \pmod{m}$。

　　证明这里就不给出，因为在百度上随便搜一搜就能找到。

　　不过，这个定理告诉我们，在$(a, m) = 1$的情况下，若存在答案，则答案不会超过$\varphi(m) - 1$。

　　考虑$a^{x} \equiv b \pmod{m}$，通过一些操作可以得到：

$a^{x - k} \equiv a^{-k}b \pmod{m}$

　　因此可以选取正整数$c$，将$x$表示为$ic + j$的形式，然后有：

$a^{ic} \equiv a^{-j}b \pmod{m}$

　　考虑预处理$a^{-j}b$，以它的值为键，最小的$j$为值存入Hash表或者Map中。

　　这样有什么用呢？你可以快速枚举$a^{ic}$，然后你将这个值在Hash表中查一查对应的最小的$j$，如果查到就可以得到答案了。

Code

 /**

  * poj

  * Problem#2417

  * Accepted

  * Time: 16ms

  * Memory: 1372l

  */

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 #include <cmath>

 using namespace std;

 typedef bool boolean;

 int p, x, a;

 typedef class HashMap {

     private:

         static const int M = ;

     public:

         int ce;

         int h[M], key[M], val[M], next[M];

         HashMap():ce(-) {    }

         void insert(int k, int v) {

             int ha = k % M;

             for (int i = h[ha]; ~i; i = next[i])

                 if (key[i] == k) {

                     val[i] = v;

                     return;

                 }

             ++ce, key[ce] = k, val[ce] = v, next[ce] = h[ha];

             h[ha] = ce;

         }

         int operator [] (int k) {

             int ha = k % M;

             for (int i = h[ha]; ~i; i = next[i])

                 if (key[i] == k)

                     return val[i];

             return -;

         }

         void clear() {

             ce = -;

             memset(h, -, sizeof(h));

         }

 }HashMap;

 int qpow(int a, int pos) {

     int pa = a, rt = ;

     for (; pos; pos >>= , pa = pa * 1ll * pa % p)

         if (pos & )

             rt = rt * 1ll * pa % p;

     return rt;

 }

 void exgcd(int a, int b, int& d, int &x, int &y) {

     if (!b)

         d = a, x = , y = ;

     else {

         exgcd(b, a % b, d, y, x);

         y -= (a / b) * x;

     }

 }

 int inv(int a, int n) {

     int d, x, y;

     exgcd(a, n, d, x, y);

     return (x < ) ? (x + n) : (x);

 }

 inline boolean init() {

     return ~scanf("%d%d%d", &p, &x, &a);

 }

 int cs;

 HashMap mp;

 inline int ind() {

     mp.clear();

     cs = sqrt(p -  + 0.5);

     if (cs == )    cs++;

     int ainv = inv(x, p), iap = a * 1ll * qpow(ainv, cs - ) % p;

     for (int i = cs - ; ~i; i--, iap = iap * 1ll * x % p)

         mp.insert(iap, i);

     int cp = qpow(x, cs), pw = ;

     for (int i = ; i < p; i += cs, pw = pw * 1ll * cp % p)

         if (~mp[pw])

             return mp[pw] + i;

     return -;

 }

 inline void solve() {

     int res = ind();

     if (res == -)

         puts("no solution");

     else

         printf("%d\n", res);

 }

 int main() {

     while (init())

         solve();

     return ;

 }

BSGS

扩展BSGS算法

　　使刚刚的问题更一般，去掉$(a, m) = 1$的条件。

　　此时逆元不一定存在，所以不能用上述的BSGS算法来做。

　　考虑去掉它们的公约数$d$。

　　得到

$a^{x - 1}\cdot\frac{a}{d} \equiv \frac{b}{d} \pmod{\frac{m}{d}}$

　　在这步中，如果$b \nmid d$，那么显然无解。

　　否则我可以令$x' = x - 1,k' = \frac{a}{d}, b'=\frac{b}{d}, m' = \frac{m}{d}$进行换元得到：

$k'a^{x'} \equiv b' \pmod{m'}$

　　如果$(a, m') = 1$，那么直接BSGS解这个方程，然后带回去算原先的$x$，否则可以继续计算$a$和$m'$的最大公约数，继续除掉它，直到$(a, m) = 1$，然后BSGS解方程。

　　因为最大公约数不为1，每次至少除以2，1和任何数互质，因此总共除的次数不会超过$\log_{2}m$。

　　但是这么做存在一个问题，假如除的次数为$k$，那么它会忽略大于等于0小于$k$的解，因此，除的时候判一下即可。

Code

 /**

  * poj

  * Problem#3243

  * Accepted

  * Time: 47ms

  * Memory: 1248k

  */

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 #include <cmath>

 #ifndef WIN32

 #define Auto "%lld"

 #else

 #define Auto "%I64d"

 #endif

 using namespace std;

 typedef bool boolean;

 int x, a, m;

 typedef class HashMap {

     private:

         static const int M = ;

     public:

         int ce;

         int h[M], key[M], val[M], next[M];

         HashMap():ce(-) {    }

         void insert(int k, int v) {

             int ha = k % M;

             for (int i = h[ha]; ~i; i = next[i])

                 if (key[i] == k) {

                     val[i] = v;

                     return;

                 }

             ++ce, key[ce] = k, val[ce] = v, next[ce] = h[ha];

             h[ha] = ce;

         }

         int operator [] (int k) {

             int ha = k % M;

             for (int i = h[ha]; ~i; i = next[i])

                 if (key[i] == k)

                     return val[i];

             return -;

         }

         void clear() {

             ce = -;

             memset(h, -, sizeof(h));

         }

 }HashMap;

 int qpow(int a, int pos, int m) {

     int pa = a, rt = ;

     for (; pos; pos >>= , pa = pa * 1ll * pa % m)

         if (pos & )

             rt = rt * 1ll * pa % m;

     return rt;

 }

 int gcd (int a, int b) {

     return (b) ? (gcd(b, a % b)) : (a);

 }

 void exgcd(int a, int b, int& d, int &x, int &y) {

     if (!b)

         d = a, x = , y = ;

     else {

         exgcd(b, a % b, d, y, x);

         y -= (a / b) * x;

     }

 }

 int inv(int a, int n) {

     int d, x, y;

     exgcd(a, n, d, x, y);

     return (x < ) ? (x + n) : (x);

 }

 inline boolean init() {

     return ~scanf("%d%d%d", &x, &m, &a) && (x || m || a);

 }

 int cs;

 HashMap mp;

 inline int ind(int pro, int x, int a, int p) {

     mp.clear();

     cs = sqrt(p -  + 0.5);

     int ainv = inv(x, p), iap = a * 1ll * qpow(ainv, cs - , p) % p;

     for (int i = cs - ; ~i; i--, iap = iap * 1ll * x % p)

         mp.insert(iap, i);

     int cp = qpow(x, cs, p), pw = pro;

     for (int i = ; i < p; i += cs, pw = pw * 1ll * cp % p)

         if (~mp[pw])

             return mp[pw] + i;

     return -;

 }

 int exind(int x, int a, int m) {

     if (a == )    return ;

     int d, k = , pro = ;

     while ((d = gcd(x, m)) != ) {

         if (a % d)    return -;

         if (pro == a)    return k;

         a /= d, m /= d, pro = (pro * 1ll * (x / d)) % m, k++;

     }

     int rt = ind(pro, x % m, a, m);

     return (~rt) ? (rt + k) : (-);

 }

 inline void solve() {

     int res = exind(x % m, a % m, m);

     if (res == -)

         puts("No Solution");

     else

         printf("%d\n", res);

 }

 int main() {

     while (init())

         solve();

     return ;

 }

ex-BSGS

最新文章

  1. 在程序中执行shell命令
  2. Kibana+Logstash+Elasticsearch 日志查询系统
  3. QueryRunner类
  4. (转)配置Website的IIS时遇到的问题与解决方法
  5. Hadoop build error java.lang.NoClassDefFoundError: org/sonatype/aether/graph/DependencyFilter
  6. 新年之际，盘点一些APP开发技巧
  7. iOS开发中遇到的bug
  8. PHP学习建议（来自老手）
  9. discuz的门户文章页中增加百度分享代码
  10. 判断iPhone设备是carplay和iPod的方法
  11. 关于ASP.NET Web Api的HelpPage文档注释问题
  12. 全方位解读&quot;CPU load average&quot;
  13. HTML5 新增的 input 事件
  14. 七.HTTP协议原理介绍
  15. Nginx调试入门
  16. Linux - 执行命令与脚本
  17. NOIP2018 模拟赛（二十二）雅礼NOI
  18. 自学Zabbix之路15.5 Zabbix数据库表结构简单解析-其他 表
  19. 高级架构进阶之HashMap源码就该这么学
  20. Android 实时视频编码—H.264硬编码

热门文章

  1. ZOJ 3690 Choosing number(矩阵)
  2. arcgis api for javascript 添加图层时设置标注，自定义符号
  3. 《大话设计模式》c++实现 之策略模式
  4. while练习题
  5. Nginx技术研究系列2-基于Redis实现动态路由
  6. [openjudge-搜索]Lake Counting(翻译及实现)
  7. Java函数接口实现函数组合及装饰器模式
  8. PYQT5学习笔记之各模块介绍
  9. 输入一串字符，检查是否可以组成friend
  10. Linux基础命令---忽略挂起信号nohup