Mambacrose

ride or die

扩展Baby Step Giant Step

| Comments

1.问题

,求最小非负整数

2.题解

则在模意义下,有如下等价代换:

然后我们继续令

模方程可以继续转化为

同理我们可以将此模方程继续转化,最后可以得到:

且此时

则有

然后我们求出在方程两边同时乘以

于是我们可以得到

因为这时候我们就可以用普通解决问题.

当然,方程也会存在无解的情况,

若存在一个的不能整除,则方程无解

3.代码
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define N 2124527
#define M 100000
using namespace std;
typedef long long LL;
LL G[M], ha[N + 1], h[N + 1], i, n, u, cas, A, B, C;
LL pow(LL a, LL b, LL p)
{
    if (b == 0) return 1;       
    LL t=a, ans=1;
    while (b)
    {
        if (b & 1) ans=(ans * t) % p;
        b >>= 1;
        t=(t * t) % p;
    }
    return ans;
}  
LL gcd(LL a, LL b)
{
    if (!b) return a;
    return gcd(b, a % b);
}
LL hash(LL x)
{
    LL i=x % N;
    while (h[i] && ha[i]!= x) i=(i + 1) % N;
    ha[i]=x;
    return i;   
}
void exBSGS(LL a, LL b, LL p)
{   
    for (LL i = 0, end = 20; i <= end; ++i) 
        if (pow(a, i, p) == b) {printf("%I64d\n", i); return;}
    LL ans=-1, koe=1, fc=0;
    LL g=gcd(a, p);
    while (g != 1)
    {
       if (b % g != 0) {printf("Math Error\n"); return;}
       p /= g, b /= g, koe*=g;
       g=gcd(a, p);
    }
    b=b * koe;
    LL m=(LL) sqrt(1.0 * p);
    if (m * m !=p) m++;
    LL res=b, sum=pow(a, m, p);
    for (LL i=0; i<=m; i++)
    {     
        LL t=hash(res);
        h[t]=i+1;
        res=(res * a) % p;
    } 
    res=sum; 
    for (LL i=1; i<=m+1; i++)
    {
        LL t=hash(res);
        if (h[t]) {ans=i * m - (h[t] - 1); break;}
        else ha[t]=0;
        res=res * sum % p;
    }
    res=b;
    for (LL i=0; i<=N; i++) h[i]=ha[i]=0;
    ans+=fc;
    if (ans > -1) printf("%I64d\n", ans); 
    else printf("Math Error\n");
}
int main()
{
    scanf("%I64d", &n);
    for (i=1; i<=n; i++)
    {
        scanf("%I64d%I64d%I64d", &A, &B, &C);   
        exBSGS(A % C, B % C, C);        
    }
    return 0;
}

Comments

comments powered by Disqus