hdu 2815 Mod Tree (扩展BSGS算法)

题意:k^D=n(%p),求最小的D  (1<=K, P, N<=10^9)

思路:出题人英文水平捉鸡。。。。

扩展BSGS算法即可,注意p>=n的时候显然是无解的,判掉。

 

BZOJ 2480: Spoj3105 Mod (扩展BSGS算法,模板)

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算法,需要注意这里没有保证(a,p)=1,因此不能直接使用BSGS算法。

我们称之为扩展BSGS算法…

但是其实并不是什么新东西,不过是几次gcd,将条件转化成满足BSGS算法的情况