bsgs (new posture)

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
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)
    if (x==0&&z==0) return 0;
    if (x==0) return -1;
    ll m=(ll)ceil(sqrt((double)p)),now=1;
    for (int i=1;i<m;i++)
        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;
    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

#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;
    return t%c;

int bsgs(ll x,ll z)
    if (!x&&!z) return 1;
    if (!z) return -1;
    ll m=(ll)ceil(sqrt((double)c)),now=z%c;
    for (int i=1;i<=m;i++)   //z*x^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