【BSGS】BZOJ3239 Discrete Logging

rir1715 2018-03-16 原文

3239: Discrete Logging

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 729 Solved: 485
[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

题解

BSGS模板题

简单说下BSGS（baby step giant step）

用于解决离散对数问题即求解a^x≡b（mod p）中的x

先处理出sqrt（p）范围内的b*a^x的值，丢进map里

然后依次求出k*a^{k*sqrt（p）}（k=1……sqrt（p））看答案是否有出现过

本质上就是分块的思想

代码

//by 减维
#include<set>
#include<map>
#include<queue>
#include<ctime>
#include<cmath>
#include<bitset>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define il inline
#define rg register
#define db double
#define mpr make_pair
#define maxn
#define inf (1<<30)
#define eps 1e-8
#define pi 3.1415926535897932384626L
using namespace std;

inline int read()
{
    int ret=0;bool fla=0;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-'){fla=1;ch=getchar();}
    while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
    return fla?-ret:ret;
}

ll x,y,p;

ll ksm(ll x,ll y,ll p)
{
    ll ret=1;x%=p;
    for(;y;y>>=1,x=x*x%p)
        if(y&1) ret=ret*x%p;
    return ret;
}

ll bsgs(ll x,ll y,ll p)
{
    map<ll,ll> mp;
    x%=p;y%=p;
    if(!x&&!y) return 1;
    if(y==1) return 0;
    if(!x) return -1;
    ll m=sqrt(p+0.5);
    ll o=y;
    for(int i=0;i<=m;++i,o=o*x%p)
        if(!mp.count(o)) mp[o]=i;
    ll tmp=ksm(x,m,p);o=tmp;
    for(int i=1;i<=m;++i,o=o*tmp%p)
        if(mp.count(o)) return ((i*m-mp[o])%p+p)%p;
    return -1;
}

int main()
{
    while(scanf("%lld%lld%lld",&p,&x,&y)!=EOF)
    {
        ll ans=bsgs(x,y,p);
        if(ans==-1) printf("no solution\n");
        else printf("%lld\n",ans);
    }
    return 0;
}