poj2417 bzoj3239 Discrete Logging（bsgs）

阅读量：4550 次

发布时间：2019-06-08

本文共 1793 字，大约阅读时间需要 5 分钟。

Description

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)

Input

Read several lines of input, each containing P,B,N separated by a space.

Output

For each line print the logarithm on a separate line. If there are several, print the smallest; if there is none, print “no solution”.

Sample Input

5 2 1

5 2 2

5 2 3

5 2 4

5 3 1

5 3 2

5 3 3

5 3 4

5 4 1

5 4 2

5 4 3

5 4 4

12345701 2 1111111

1111111121 65537 1111111111

Sample Output

no solution

9584351

462803587

Hint

The solution to this problem requires a well known result in number theory that is probably expected of you for Putnam but not ACM competitions. It is Fermat’s theorem that states

B(P-1) == 1 (mod P)

for any prime P and some other (fairly rare) numbers known as base-B pseudoprimes. A rarer subset of the base-B pseudoprimes, known as Carmichael numbers, are pseudoprimes for every base between 2 and P-1. A corollary to Fermat’s theorem is that for any m

B(-m) == B(P-1-m) (mod P) .

分析：

bsgs

tip

板子打对，万事ok

费马定理的推论
X^(-m)≡X^(p-1-m) (mod p)
p为素数

终于知道为什么tmp是这么计算的了

这里写代码片#include
     
      #include
      
       #include
       
        #include
        #define ll long longusing namespace std;ll x,z,p;map
         
           mp;ll KSM(ll a,ll b,ll p){    ll t=1;    a%=p;    while (b)    {        if (b&1)            t=(t%p*a%p)%p;        b>>=1;        a=(a%p*a%p)%p;    }    return t%p;}ll bsgs(ll x,ll z,ll p){    mp.clear();    x%=p; z%=p;    if (x==0&&z==0) return 0;    if (x==0) return -1;    ll m=(ll)ceil(sqrt((double)p)),now=1;    mp[1]=m+1;    for (ll i=1;i

转载于:https://www.cnblogs.com/wutongtong3117/p/7673237.html

你可能感兴趣的文章