题意：k^D=n(%p),求最小的D (1<=K, P, N<=10^9) 思路：出题人英文水平捉鸡。。。。 扩展BSGS算法即可，注意p>=n的时候显然是无解的，判掉。 /* *********************************************** Author :111qqz Created Time :Mon 24 Jul 2017 09:43:41 PM CST File Name :2815.cpp ************************************************ */ #include <cstdio> #include …

Description 已知数a,p,b，求满足a^x≡b(mod p)的最小自然数x。 Input  每个测试文件中最多包含100组测试数据。  每组数据中，每行包含3个正整数a,p,b。  当a=p=b=0时，表示测试数据读入完全。 Output  对于每组数据，输出一行。  如果无解，输出“No Solution”（不含引号），否则输出最小自然数解。 Sample Input 5 58 33 2 4 3 0 0 0 Sample Output 9 No Solution HINT  100%的数据，a,p,b≤1e9。 2016.3.29新加数据一组 by 1430586275 思路：BSGS算法，需要注意这里没有保 …

离散对数（Discrete Logarithm）问题是这样一个问题，它是对于模方程 a^x=b(mod prime)，求满足条件的X，或者得出不存在这样的X 最暴力的思路，那么就是枚举x? 根据费马小定理，只需要枚举[0,p-1) 但是还是很大...我们不禁想到把x写成x=A*m+B的形式，m=ceil(sqrt(p)) 因此有 ，变形得到 然后预处理一边存到map中，从小到大枚举另一边看是否存在... 我们可以设 ，其中 , ，这样的话化简后的方程就是 就可以不用求出逆元，要注意只是不用求出逆元，而不是没有用到逆元的存在 就可以不用求出逆元，要注意只是不用求出逆元，而不是没有用到逆元的存在 就可以不用求出逆元，要注意只是不用求出 …

题目链接 题意： Given a prime P, 2 <= P < 231, an integer B, 2 <= B < P, and an integer N, 1 <= N < P, compute the discrete logarithm of N, base B, modulo P. That is, find an integer L such that BL == N (mod P) 思路：bsgs算法 详情见BSGS算法笔记 然后被map的count坑了一下？ 我想判断map中某个key是否存在，用count会TLE，find也会TLE,[]可以通过....不太懂，复杂度不都 …