2019牛客多校第五場--C generator 2 (BSGS優化)

一.題意

題目連結

二.分析

①手動遞推或矩陣快速幂，推出：xn=b + ba + ba^2 + ba^3 + ... + ba^(n - 1) + x0a^n

②用等比數列求和公式，然後

因為要求n，把a^n單獨放出來：

③經典的BSGS，原算法複雜度

肯定TLE

因為有這步：long long m=ceil(sqrt(C))

需要用分塊的思想，即利用“大步小步”算法精髓，大步1e6，小步1e4（還會具體講）

等式左邊和右邊人為各設定一個枚舉範圍，另外注意特判即可

三.代碼

正解：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int t1 = 1001,t2 = 1e6;
struct hash{
    static const int N=1e6+10;
    static const int mod=2000000;
    int head[mod+10],hs[N],nxt[N],id[N];
    int tot;
    void init()
    {
        memset(head,-1,sizeof(head));
        tot=0;
    }
    void insert(int x,int y)
    {
        int k=x%mod;
        hs[tot]=x;
        id[tot]=y;
        nxt[tot]=head[k];
        head[k]=tot++;
    }
    ll find(ll x)
    {
        int k=x%mod;
        for(int i=head[k];i!=-1;i=nxt[i])
        {
            if(hs[i]==x)
            {
                return id[i];
            }
        }
        return -1;
    }
}hs;
ll power(ll a,ll b,ll p)
{
    ll ans=1;
    while(b)
    {
        if(b&1)
        ans=ans*a%p;
        a=a*a%p;
        b>>=1;
    }
    return ans;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        ll n,x0,a,b,p;
        scanf("%lld%lld%lld%lld%lld",&n,&x0,&a,&b,&p);
        ll s=power(a,t1,p);
        ll x=1;
        hs.init();
        for(int i=1;i<=t2;i++)
        {
            x=1ll*x*s%p;
            if(hs.find(x)==-1)
            hs.insert(x,i*t1);
        }
        ll mu=(b+1ll*a*x0%p-x0+p)%p;
        ll inv=power(mu,p-2,p);
        int q;
        scanf("%d",&q);
        while(q--)
        {
            ll v;
            scanf("%lld",&v);
            if(!a)
            {
                if(v==x0)
                printf("0\n");
                else if(v==b)
                {
                    printf("1\n");
                }
                else
                printf("-1\n");
                continue;
            }
            if(a==1)
            {
                ll ans=(v-x0+p)*power(b,p-2,p)%p;
                if(ans<n)
                printf("%lld\n",ans);
                else
                printf("-1\n",ans);
                continue;
            }
            ll ans=p+1;
            v=(v*(a-1)%p+b)*inv%p;
            ll y=v;
            for(int i=0;i<=t1;i++)
            {
                if(hs.find(y)!=-1)
                ans=min(ans,hs.find(y)-i);
                y=y*a%p;
            }
            if(ans==p+1||ans>n)
            printf("-1\n");
            else
            printf("%lld\n",ans);
        }
    }
    return 0;
}
           

貼一個用傳統BSGS方法卡過的代碼，%%%csl，優化版BSGS待更

然而我自己交上去TLE。。。

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
#define ENABLE_FREAD
 
namespace io_impl
{
inline bool maybe_digit(char c)
{
    return c >= '0' && c <= '9';
}
 
inline bool maybe_decimal(char c)
{
    return (c >= '0' && c <= '9') || (c == '.');
}
 
struct io_s
{
 
    bool negative;
    bool ok = true;
    char ch = next_char();
 
    int precious = 6;
    long double epslion = 1e-6;
 
#ifdef ENABLE_FREAD
    inline char next_char()
    {
        static char buf[100000], *p1 = buf, *p2 = buf;
        return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
    }
#else
    inline char next_char() const
    {
        return getchar();
    }
#endif
 
    /// read int
 
    template <typename T>
    inline bool rn(T& _v)
    {
        negative = false;
        _v = 0;
        while (!maybe_digit(ch) && ch != EOF)
        {
            negative = ch == '-';
            ch = next_char();
        };
        if (ch == EOF) return ok = false;
        do
        {
            _v = (_v << 1) + (_v << 3) + ch - '0';
        } while (maybe_digit(ch = next_char()));
        if (negative) _v = -_v;
        return true;
    }
 
    template <typename T>
    inline void rn_unsafe(T& _v)
    {
        negative = false;
        _v = 0;
        while (!maybe_digit(ch))
        {
            negative = ch == '-';
            ch = next_char();
        };
        do
        {
            _v = (_v << 1) + (_v << 3) + ch - '0';
        } while (maybe_digit(ch = next_char()));
        if (negative) _v = -_v;
    }
 
    template <typename T>
    inline T rn()
    {
        T v = T();
        rn_unsafe(v);
        return v;
    }
 
    inline int ri() { return rn<int>(); }
    inline ll rll() { return rn<ll>(); }
 
    /// read unsigned
 
    template <typename T>
    inline bool run(T& _v)
    {
        _v = 0;
        while (!maybe_digit(ch) && ch != EOF) ch = next_char();
        if (ch == EOF) return ok = false;
        do
        {
            _v = (_v << 1) + (_v << 3) + ch - '0';
        } while (maybe_digit(ch = next_char()));
        return true;
    }
 
    template <typename T>
    inline void run_unsafe(T& _v)
    {
        _v = 0;
        while (!maybe_digit(ch)) ch = next_char();
        do
        {
            _v = (_v << 1) + (_v << 3) + ch - '0';
        } while (maybe_digit(ch = next_char()));
    }
 
    template <typename T>
    inline T run()
    {
        T v = T();
        run_unsafe(v);
        return v;
    }
 
    /// read double
 
    template <typename T>
    inline bool rd(T& _v)
    {
        negative = false;
        _v = 0;
        while (!maybe_digit(ch) && ch != EOF)
        {
            negative = ch == '-';
            ch = next_char();
        };
        if (ch == EOF) return ok = false;
        do
        {
            _v = (_v * 10) + (ch - '0');
        } while (maybe_digit(ch = next_char()));
        static int stk[70], tp;
        if (ch == '.')
        {
            tp = 0;
            T _v2 = 0;
            while (maybe_digit(ch = next_char()))
            {
                stk[tp++] = ch - '0';
            }
            while (tp--)
            {
                _v2 = _v2 / 10 + stk[tp];
            }
            _v += _v2 / 10;
        }
        if (ch == 'e' || ch == 'E')
        {
            ch = next_char();
            static bool _neg = false;
            if (ch == '+')
                ch = next_char();
            else if (ch == '-')
                _neg = true, ch = next_char();
            if (maybe_digit(ch))
            {
                _v *= pow(10, run<ll>() * (_neg ? -1 : 1));
            }
        }
        if (negative) _v = -_v;
        return true;
    }
 
    template <typename T>
    inline T rd()
    {
        T v = T();
        rd(v);
        return v;
    }
 
    /// read string
 
    inline int gets(char* s)
    {
        char* c = s;
        while (ch == '\n' || ch == '\r' || ch == ' ') ch = next_char();
        if (ch == EOF) return (ok = false), *c = 0;
        do
        {
            *(c++) = ch;
            ch = next_char();
        } while (ch != '\n' && ch != '\r' && ch != ' ' && ch != EOF);
        *(c++) = '\0';
        return static_cast<int>(c - s - 1);
    }
 
    inline int getline(char* s)
    {
        char* c = s;
        while (ch == '\n' || ch == '\r') ch = next_char();
        if (ch == EOF) return (ok = false), *c = 0;
        do
        {
            *(c++) = ch;
            ch = next_char();
        } while (ch != '\n' && ch != '\r' && ch != EOF);
        *(c++) = '\0';
        return static_cast<int>(c - s - 1);
    }
 
    inline char get_alpha()
    {
        while (!isalpha(ch)) ch = next_char();
        const char ret = ch;
        ch = next_char();
        return ret;
    }
 
    inline char get_nonblank()
    {
        while (isblank(ch)) ch = next_char();
        const char ret = ch;
        ch = next_char();
        return ret;
    }
 
    inline char get_char()
    {
        const char ret = ch;
        ch = next_char();
        return ret;
    }
 
    template <typename T>
    inline void o(T p)
    {
        static int stk[70], tp;
        if (p == 0)
        {
            putchar('0');
            return;
        }
        if (p < 0)
        {
            p = -p;
            putchar('-');
        }
        while (p) stk[++tp] = p % 10, p /= 10;
        while (tp) putchar(stk[tp--] + '0');
    }
 
    template <typename T>
    inline void od(T v)
    {
        static int stk[70], tp;
        tp = 0;
        if (fabs(v) < epslion / 10)
        {
            putchar('0');
            if (precious > 0)
            {
                putchar('.');
                for (int i = 0; i < precious; ++i) putchar('0');
            }
            return;
        }
        else
        {
            if (v < 0)
            {
                v = -v;
                putchar('-');
            }
            v += epslion / 2;
            T p = floor(v) + epslion / 10;
            while (fabs(p) > 1 - epslion)
            {
                stk[++tp] = fmod(p, 10), p /= 10;
            }
            while (tp) putchar(stk[tp--] + '0');
        }
        if (precious == 0) return;
        putchar('.');
        v -= floor(v);
        for (int i = 0; i < precious; ++i)
        {
            v *= 10;
            putchar((int)floor(v) + '0');
            v = fmod(v, 1);
        }
    }
 
    /// Enhancement
 
    typedef void io_operator(io_s& v);
    typedef char* charptr;
 
    template <typename T>
    inline io_s& operator>>(T& x)
    {
        if (numeric_limits<T>::is_signed)
            rn(x);
        else
            run(x);
        return *this;
    }
 
    template <typename T>
    inline io_s& operator<<(const T& x);
 
    inline io_s& operator<<(io_operator* v)
    {
        v(*this);
        return *this;
    }
 
    operator bool() const { return ok; }
 
    void set_precious(int x)
    {
        precious = x;
        epslion = pow(10, -x);
    }
};
 
template <>
inline io_s& io_s::operator>>(char*& x)
{
    gets(x);
    return *this;
}
 
template <>
inline io_s& io_s::operator>>(float& x)
{
    rd(x);
    return *this;
}
 
template <>
inline io_s& io_s::operator>>(double& x)
{
    rd(x);
    return *this;
}
 
template <>
inline io_s& io_s::operator>>(long double& x)
{
    rd(x);
    return *this;
}
 
template <>
inline void io_s::o(const char* p)
{
    printf(p);
}
 
template <>
inline void io_s::o(const char p)
{
    putchar(p);
}
 
template <>
inline void io_s::o(float p)
{
    od(p);
}
 
template <>
inline void io_s::o(double p)
{
    od(p);
}
 
template <>
inline void io_s::o(long double p)
{
    od(p);
}
 
template <typename T>
inline io_s& io_s::operator<<(const T& x)
{
    o(x);
    return *this;
}
 
inline void new_line(io_s& v)
{
    v.o('\n');
}
 
io_s::io_operator* nl = new_line;
} // namespace io_impl
 
using namespace io_impl;
 
io_s io;
 
namespace solution
{
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
ll Pow(ll a, ll n, ll p)
{
    ll t = 1;
    for (; n; n >>= 1, (a *= a) %= p)
        if (n & 1) (t *= a) %= p;
    return t;
}
 
ll inv(ll x, ll p) { return Pow(x, p - 2, p); }
struct B
{
    const int mod = 524287;
    const int MOD = 1e9 + 7;
    int tot;
    int h[524288], next[524288], L[524288], v[524288];
    int Find(long long x)
    {
        int k = h[x & mod];
        while (k != 0)
            if (L[k] == x)
                return v[k];
            else
                k = next[k];
        return -1;
    }
 
    void Add(long long e, int i)
    {
        tot++;
        next[tot] = h[e & mod];
        L[tot] = e;
        v[tot] = i;
        h[e & mod] = tot;
    }
    long long V, m;
    void Init(int a, int n)
    {
        memset(h, 0, sizeof(h));
        memset(next, 0, sizeof(next));
        memset(L, 0, sizeof(L));
        memset(v, 0, sizeof(v));
        tot = 0;
        long long e = 1, i;
        m = (long long)sqrt(n + 0.5);
        while (m * m < n) m++;
        while ((m - 1) * (m - 1) >= n) m--;
        V = inv(Pow(a, m, n), n);
        Add(1, 0);
        for (int i = 1; i < m; i++)
        {
            e = e * a % n;
            if (Find(e) == -1)
                Add(e, i);
        }
    }
 
    long long BSGS(int a, int b, int n) //a^x = b % n
    {
 
        //v = Pow(Pow(a, m, n), n - 2, n);
        for (int i = 0; i < m; i++)
        {
            if (Find(b) != -1) return i * m + Find(b);
            b = b * V % n;
        }
        return -1;
    }
} S;
 
int main()
{
    int T;
    io >> T;
    while (T--)
    {
        ll n, a1, c, d, p;
        io >> n >> a1 >> c >> d >> p;
        if (c == 0)
        {
            int q;
            io >> q;
            ll an;
            while (q--)
            {
                io >> an;
                if (an == a1)
                    io << 0 << nl;
                else if (an == d && n > 1)
                    io << 1 << nl;
                else
                    io << -1 << nl;
            }
        }
        else if (c == 1)
        {
            int q;
            io >> q;
            ll an;
            while (q--)
            {
                io >> an;
                if (d == 0)
                {
                    if (an == a1)
                        io << 0 << nl;
                    else
                        io << -1 << nl;
                }
                ll ans = ((an - a1 + p) % p) * inv(d, p) % p;
                if (ans >= n)
                    io << -1 << nl;
                else
                    io << ans << nl;
            }
        }
        else
        {
            ll x0 = d * inv((1 - c + p) % p, p) % p;
            int q;
            ll an;
            io >> q;
            if (x0 == a1)
            {
                while (q--)
                {
                    io >> an;
                    if (an == a1)
                        io << 0 << nl;
                    else
                        io << -1 << nl;
                }
            }
            else
            {
                S.Init(c, p);
                while (q--)
                {
                    io >> an;
                    ll t = ((an - x0 + p) % p) * inv((a1 - x0 + p) % p, p) % p;
                    ll ans = S.BSGS(c, t, p);
                    if (ans != -1 && ans >= n) ans = -1;
                    io << ans << nl;
                }
            }
        }
    }
    return 0;
}
 
} // namespace solution
 
int main()
{
    return solution::main();
}
           

三.代碼