# 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