[Luogu]P3306 [SDOI2013] 随机数生成器
本文最后更新于 138 天前,其中的信息可能已经有所发展或是发生改变。

Before the Beginning

转载请将本段放在文章开头显眼处,如有二次创作请标明。

原文链接:https://www.codein.icu/lp3306/

题意

$\forall i \in \left\{ 1,2,\ldots\right\},x_{i+1} \equiv a \times x_i + b \pmod{p}$

求 $\min i,x_i \equiv t \pmod{p}$

解法

$x_i$ 看起来就像是等比数列,可以利用高中知识进行构造。

设 $x_{i+1} + c = a \times (x_i + c)$,展开有 $x_{i+1} = a \times x_i + (a-1)c$

解得 $c = \dfrac{b}{a-1}$,还原出数列:

$y_i = x_i + \dfrac{b}{a-1}$

$y_{i+1} = a \times y_i$

求 $\min i,x_i = t$ 即求 $\min i,y_i = t + \dfrac{b}{a-1}$

其中 $y_1$ 是定值。

$y_i = y_1 \times a^{i-1} = t + \dfrac{b}{a-1}$

$a^{i-1} = \dfrac{t + \dfrac{b}{a-1}}{y_1}$

即求:

$a^{i-1} \equiv \dfrac{t + \dfrac{b}{a-1}}{x_1 + \dfrac{b}{a-1}} \pmod{p}$

即:

$A^B \equiv C \pmod{p}$

使用 BabyStepGiantStep 求解即可。

特判 $a = 0,1$ 时的情况。

#include <cstdio>
#include <cmath>
#include <cstring>
#define ll long long
int T;
ll p,a,b,x1,t;
ll fastpow(ll x,ll k)
{
    ll res = 1;
    while(k)
    {
        if(k & 1) res = (res * x) % p;
        x = (x * x) % p;
        k >>= 1;
    }
    return ((res % p) + p) % p;
}
ll inv(ll x) { return fastpow(x, p - 2); }
struct BetterListHashTable
{
    static const int mod = 100103;
    static const int maxn = 2e5 + 100;
    struct node
    {
        int next, key, val;
    } A[maxn + 10];
    int head[mod + 100], tot;
    void clear() { memset(head, 0, sizeof(head)), tot = 0; }
    int hash(int x)
    {
        int res = x % mod;
        if (res < 0) res += mod;
        return res;
    }
    int& operator[](int key)
    {
        int pos = hash(key);
        for (int p = head[pos]; p; p = A[p].next)
            if (A[p].key == key) return A[p].val;
        A[++tot].next = head[pos], A[tot].key = key, A[tot].val = 0, head[pos] = tot;
        return A[tot].val;
    }
    int* find(int key)
    {
        int pos = hash(key);
        for (int p = head[pos]; p; p = A[p].next)
            if (A[p].key == key) return &A[p].val;
        return NULL;
    }
} HT;
ll exgcd(ll a,ll b,ll &x,ll &y)
{
    if(b == 0){x = 1,y = 0;return a;}
    ll g = exgcd(b,a%b,y,x);y -= (a / b) * x;
    return g;
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%lld %lld %lld %lld %lld", &p, &a, &b, &x1, &t);
        if(x1 == t) {puts("1");continue;}
        if(a == 1 && b == 0) {puts("-1");continue;}
        if(a == 0)
        {
            if(b == t) {puts("2");continue;}
            puts("-1");continue;
        }
        if(a == 1)
        {
        //t = x_1 + (i-1) \times b + k \times p
        //t - x_1 = (i-1) \times b + k2 \times p
            ll k1,k2,g;
            g = exgcd(b,p,k1,k2);
            ll c = (((t - x1) % p) + p) % p;
            if(c % g) {puts("-1");continue;}
            k1 = (((k1 * c / g % p) + p) % p) + 1;
            printf("%lld\n", k1);
            continue;
        }
        HT.clear();
        ll c = (b * inv(a - 1)) % p;
        ll C = ((t + c) * inv(x1 + c)) % p;
        ll sqrtp = std::ceil(std::sqrt(p));
        ll tmp = C;
        for (int i = 0; i <= sqrtp; ++i) HT[tmp] = i, tmp = (tmp * a) % p;
        ll sq = fastpow(a,sqrtp);
        tmp = sq;
        for (int i = 1; i <= sqrtp; ++i)
        {
            int* ans = HT.find(tmp);
            if(ans != NULL) { printf("%lld\n",i * sqrtp - *ans + 1); goto end; }
            tmp = (tmp * sq) % p;
        }
        puts("-1");
    end:;
    }
    return 0;
}
本文标题:[Luogu]P3306 [SDOI2013] 随机数生成器
本文作者:Clouder
本文链接: https://www.codein.icu/lp3306/
转载请标明。
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇