2019牛客暑期多校訓練（第五場）C-generator 2

題目描述

There is a sequence of length n:x0,x1,x2,…,xn−1. Please answer Q queries. Each query consists of one integer v, asking the minimum index i such that xi=v. If the sequence doesn’t have any number with value v, you only need to output -1.

Does the problem look simple? Surprise! The value of n may be as large as 1018!

Because n is so large. We will only give you four integers x0,a,b,p to generate the sequence. For all i>0, the sequence is generated as xi=(a⋅xi−1+b)mod p.

輸入描述:

The first line of input contains an integer T (T≤4) denoting there are T tests in the input.

Each test contains Q+2 lines.

The first line of each test contains five integers n,x 0,a,b,p (1≤n≤1018,0≤xp,a,b<p≤109+9, p is a prime number).

The second line contains one integer Q (Q≤1000).

Each of the following Q lines contains one integer v (0≤v<p).

輸出描述:

For each query, print one integer as the answer in one line.

示例1

輸入

1000000009 1 1 1 1000000009

1000000008

1000000007

100000009 1 1 1 1000000009

1000000008

1000000000000000000 1 5 0 1000000007

1000000006

12345678

1234567

輸出

1000000008

1000000007

1000000006

-1

381838283

500000003

652614354

581802189

說明

For the first test, the sequence looks like 1, 2, 3, …, 1000000008, 0. So the position of the first occurrence of value v is v - 1 except for value 0 which occurs at 1000000008.

示例2

輸入

1000000000000000000 5 2 2 1000000007

5 1 0 3 950000017

輸出

115068150

342074

115068151

-1

題意

已知x[i]=(a*x[i-1]+b)%p，求滿足等式的x數組的下标，且該下标小于n。若不存在則輸出-1。

思路

BSGS算法（北上廣深算法，拔山蓋世算法）。

首先，我們可以根據遞推式求出x[n]關于x[0]的表達式。

然後。。。然後。。。然後。。。

就沒有然後了。

發現是一個BSGS的式子。

求就完了。

坑點

真特麼多。

首先，這題時間卡的很緊，如果用map哈希的話很容易逾時，是以我後來用了unordered_map。

然後，我隊友用鍊式前向星手寫哈希跑了627ms，tql。

大佬的CSDN個人首頁

之後還加了很多小優化，具體的就看BSGS和initBSGS函數部分的代碼吧。

代碼

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=1e5+5;

ll quickpow(ll a,ll b,ll mod)
{
    ll ans=1;
    while(b)
    {
        if(b&1)
            ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}

unordered_map<int,int> M;
ll up,down,mul;

void initBSGS(ll y,ll p)
{
    M.clear();
    up=ceil(pow(p,2.0/3));
    down=ceil(pow(p,1.0/3));
    ll num=1;
    for(int i=0; i<=up; i++)
    {
        if(i==up)
            mul=num;
        M[num]=i;
        num=num*y%p;
    }
}

ll BSGS(ll y,ll z,ll p)
{
    ll num=quickpow(z,p-2,p);
    for(int i=1; i<=down+1; i++)
    {
        num=num*mul%p;
        if(M.count(num))
            return i*up-M[num];
    }
    return -1;
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        ll n,x0,a,b,q,v,mod;
        scanf("%lld%lld%lld%lld%lld",&n,&x0,&a,&b,&mod);
        initBSGS(a,mod);
        scanf("%lld",&q);
        while(q--)
        {
            scanf("%lld",&v);
            if(a==0)
            {
                if(v==x0)
                    printf("0\n");
                else if(v==b&&n>=1)
                    printf("1\n");
                else
                    printf("-1\n");
            }
            else if(a==1)
            {
                if(b==0)
                    printf("%d\n",v==x0?0:-1);
                else
                {
                    int invb=quickpow(b,mod-2,mod);
                    v=((v-x0+mod)%mod)*invb%mod;
                    printf("%d\n",v<n?v:-1);
                }
            }
            else
            {
                if(x0==0&&b==0)
                    printf("%d\n",v==0?0:-1);
                else
                {
                    ll num=quickpow((((1-a+mod)%mod)*x0%mod-b+mod)%mod,mod-2,mod)*((((1-a+mod)%mod)*v%mod-b+mod)%mod)%mod;
                    ll ans=BSGS(a,num,mod);
                    if(ans<n)
                        printf("%lld\n",ans);
                    else
                        printf("-1\n");
                }
            }
        }
    }
    return 0;
}

2019牛客暑期多校訓練（第五場）C-generator 2