BZOJ 3239--Discrete Logging(BSGS)

3239: Discrete Logging

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 635 Solved: 413
[Submit][Status][Discuss]

Description

Given a prime P, 2 <= P < 2³¹, an integer B, 2 <= B < P, and an integer N, 2 <= N < P, compute the discrete logarithm of N, base B, modulo P. That is, find an integer L such that

    B^L= 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".

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）

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

0
1
3
2
0
3
1
2
0
no solution
no solution
1
9584351
462803587

题目链接：

　　　　http://www.lydsy.com/JudgeOnline/problem.php?id=3239

Solution

　　　　BSGS的模板题。。。。

　　　　对于本题的做法。。一般是先设 L = i * e + j 或 L = i * e - j 。。。

　　　　e = ceil（sqrt（P））。。就是假如算出 sqrt（P）= 1.14 ，e就等于2，往大的取整

　　　　然后枚举 i 和 j 的值就能做到 O（sqrt（P））。。。

代码

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<iostream>

#include<map>

#define LL long long

using namespace std;

LL P,B,N,e,now;

map<LL,int>mp;

LL pow(LL p,LL q){

    LL s=1;

    while(q){

        if(q&1) s=s*p%P;

        q>>=1;

        p=p*p%P;

    }

    return s;

}

void solve(){

    mp.clear();

    if(N==1 && B>0){

        printf("0\n");

        return;

    }

    if( (!B) && (!N) ){printf("1\n");return;}

    if(!B){printf("no solution\n");return;}

    e=ceil(sqrt(P));

    now=N%P;

    for(int j=1;j<=e;j++){

        now=now*B%P;

        if(!mp[now]) mp[now]=j;

    }

    B=pow(B,e);

    now=1;

    for(int i=1;i<=e;i++){

        now=now*B%P;

        if(mp[now]>0){

            N=e*i-mp[now];

            printf("%lld\n",N);

            return;

        }

    }

    printf("no solution\n");

    return;

}

int main(){

    while(scanf("%lld%lld%lld",&P,&B,&N)!=EOF) solve();

    return 0;

}

This passage is made by Iscream-2001.

巴特西