bsgs (new posture)

preface:
Today, in the first hu test of senior high school, an exbsgs was issued
(I was also asked to help create data. However, the data I created was very watery and violent. In the end, Shu Shen helped...)
But I don't think it's time to learn new knowledge,
DP told me that there was a kind of strange skill, so he came to fill the hole...

I studied bsgs before
At that time, we used this formula:
x^y(mod p)=z
y=km+i(m=sqrt(p))
Process out: x^i, throw it into a map
x^i=z*x^(-km) (mod p)
When p is prime, we can calculate the inverse element of x^km
Enumerate k and search in map

ll bsgs(ll x,ll z,ll p)
{
    mp.clear();  
    x%=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 (int i=1;i<m;i++)
    {
        now=(now*x)%mod;
        if (!mp[now]) mp[now]=i;  
    ll inv=1,tmp=KSM(x,p-m-1,p); 
    for (int k=0;k<m;k++)
    {
        int i=mp[(z*inv)%p]; 
        if (i)
        {
            if (i==m+1) i=0;
            return k*m+i;
        }
        inv=(inv*tmp)%p;
    } 
    return -1;
}

However, when p is not prime,

We can't find the inverse element
Therefore, we need to change the simplification method of the following formula:

Let y = k m − i, m=sqrt(p), then (xm)k * x ^ (− i) ≡ z(modp)
Transfer, get (xm)k ≡ z * xi(modp)
First, enumerate i from 0 − m, and store the value of z * xi in the hash table;
Then, enumerate k from 1 − m, calculate (am)i, check the table, if there is a value equal to it, then the km − i obtained at that time is the minimum value

be careful:
k cannot be 0, otherwise km − i may be negative
In order to minimize km − i, we should record the maximum value of i in the hash table

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<map>
#define ll long long

using namespace std;

ll a,b,c;
map<ll,int> mp;

ll KSM(ll a,ll b)
{
    ll t=1;
    while (b)
    {
        if (b&1) t=(t%c*a%c)%c;
        b>>=1;
        a=(a%c*a%c)%c;
    }
    return t%c;
}

int bsgs(ll x,ll z)
{
    mp.clear();
    x%=c;
    if (!x&&!z) return 1;
    if (!z) return -1;
    ll m=(ll)ceil(sqrt((double)c)),now=z%c;
    mp[now]=m+1;
    for (int i=1;i<=m;i++)   //z*x^i
    {
        now=(now%c*x%c)%c;
        mp[now]=i;
    }
    ll num=1,tmp=KSM(x,m);
    for (int k=1;k<=m;k++)
    {
        num=(num*tmp)%c;     //
        int i=mp[num];
        if (i)
        {
            if (i==m+1) i=0;
            return (k*m-i+c)%c;
        }   
    }
    return -1;
}

int main()
{
    while (scanf("%lld%lld%lld",&a,&b,&c)!=EOF&&(a+b+c)!=0)
    {
        int ans=bsgs(a,b);
        if (ans==-1) printf("No Solution\n");
        else printf("%d\n",ans);
    }
    return 0;
}

Posted on Thu, 30 Apr 2020 08:29:18 -0700 by PoOP