ACM数论总结5

       这周的话总体学习的东西不是很多，一开始前三天还比较稳定，后来的时候就因为补课以及课程设计，以及最后的大逃亡，就没怎么有空训练了，确实是有一些浮躁的。

回顾这一周，只剩下一些关于BGSS的博客没有看完，所以先复习了关于BGSS的算法，

这周复习了BSGS算法，因为就剩下这几篇博客没有读了，常用的还是之前说过的map这个用法，因为单独的去写哈希表实在是比较麻烦，

例题：P3846 [TJOI2007] 可爱的质数/【模板】BSGS - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

模板：

#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int mod = 1000000007;
 
ll BSGS(ll a, ll b, ll mod) {
    map mp;
    ll mm = 1;
    ll tt = sqrt(mod) + 1;
    for (int i = 1; i <= tt; i++) {
        mm = mm * a % mod;
        mp[b * mm % mod] = i;
    }
    ll now = mm;
    for (int i = 1; i <= tt; i++) {
        if (mp[now]) 
            return (ll)i * tt - mp[now];
        now = now * mm % mod;
    }
    return -1;
}
 
int main() {
    
    int a, b, n;
    cin >> a >> b >> n;
    ll ans =BSGS(b, n, a);
    if (ans == -1)
        cout << "no solution" << endl;
    else
        cout << ans << endl;
   
}

 模板就用写的这个map就可以了，会比较好理解一些。

还有就是扩展BSGS算法（话说我一直看错了这个算法的字母），区别的话上期的总结我也说过了就是扩展BSGS可以解决底数a与模数p不互质的这种状况，推理的话就复习这篇博客就行：

(4条消息) 扩展BSGS 学习笔记_forever_shi的博客-CSDN博客_扩展bsgs

P4195 【模板】扩展 BSGS/exBSGS - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 

        新学习的内容太致就只有这些了，相对来说时间确实分配的不是特别好，比较好的就是现在每天都训练蓝桥杯的题目，数论也是每天都会看题目，做题目，遇见的最大困难就是有的题目只有c++的代码，python的就很少很少，有时候用python写题目的时候还是挺麻烦的因为速度相对来说不是很快，这一两天先休整一下，平稳情绪，继续做题。