【今日の精進】ABC270G - Sequence in mod P

毎日格上の問題を倒すやつの62日目です。

問題リンク

atcoder.jp

問題概要

という漸化式があるよ。

となるような最小の を求めるか、そんなものはないと宣言してね。

解法

の場合は後がめんどいので先に処理しましょう。これは適切に場合分けするだけです。

それ以外の場合、これは典型的な離散対数問題です。そのため、Baby-Step Giant-Stepを使用しましょう。

これは、 までを先に求めておいたのち、 から ずつ遡って求めておいたところにぶつかったら答えがわかるというものです。

遡っていく動作は、適切な前計算のもと簡単に求められます。

提出コード

backet=32000
T=int(input())
for _ in range(T):
    P,A,B,S,G=map(int,input().split())
    if A==0:
        if S==G:
            print(0)
        elif G==B:
            print(1)
        else:
            print(-1)
        continue
    pos={}
    ans=-1
    div=1
    sub=0
    for i in range(backet):
        if S==G:
            ans=i
            break
        sub=(sub*A+B)%P
        div*=A
        div%=P
        pos[S]=i
        S=(S*A+B)%P
    if ans!=-1:
        print(ans)
        continue
    div=pow(div,-1,P)
    for i in range(backet):
        if G in pos:
            ans=i*backet+pos[G]
            break
        G=((G-sub)*div)%P
    print(ans)

atcoder.jp

感想

アルゴリズム調べたらこの問題の解説しか出てこんかった