[ABC 270] G. Sequence in mod P ★

문제 링크

버추얼을 돌면서 만난 문제이다.

 

처음에는 함수형 그래프에서 사이클을 다루는 알고리즘 floyd cycle finding을 떠올렸는데, 이내 입력을 보아하니 안 될 것 같아서 접고 수식을 정리해봤다.

$G=A^nS+B\cdot \frac {A^n-1}{A-1}$이 나왔는데, $n$을 결정하는 것이 난관이였다.

식을 $n$에 대해서 정리하고 이산 로그로 구할 수 있을까라는 생각을 했고, 딱히 발전이 없던 차에 시간이 끝났다.

 

알고 보니 이산 로그도 풀이가 될 수 있고, 혹은 baby-step giant-step이라는 알고리즘을 사용할 수도 있었다.

사실 이산 로그를 구할 때 이 알고리즘이 들어간다.

 

아무튼 baby step giant step의 원리를 이해했다. 이것으로 이산 로그를 구할 수 있다는 사실도 인지했다.

 

이 문제를 잘 이해하면 4357번: 이산 로그와 16808번: Idetity Function도 풀 수 있을 것이라 기대된다.

UPD - 4357은 바로 맞혔다.

 

참고할 만한 자료들로는 다음이 있다:

• 위키피디아 - 이산로그: 기본적인 정의를 확인할 수 있다.
• rkm0959 - 원시근, 이산로그, 이산제곱근: 다소 어렵지만 관련 개념과의 관계를 이해할 수 있다.
• aruz - 이산 로그: 심플한 구현을 확인할 수 있다.
• barking dog - 이산 로그: Crypto 쪽으로 깊이 있게 다루는데, 목차 2개 정도만 봐도 충분해 보인다.
• nyan101 - 이산 로그: 마찬가지이다.

다시 돌아와서, 앞서 언급한 두 가지 방식으로 문제를 풀어 보겠다.

 

baby-step giant-step을 이용한 풀이

$f^n(x):=\overbrace{f\circ f\circ \cdots \circ f}^n(x)$라고 하면, $F(x):=Ax+B$일 때 $F^n(S)\equiv G\pmod{P}$인 최소의 $n$을 찾는 문제가 된다.

$g=F^{-1}$이라고 하면, $F^m(S)\equiv g^{n-m}(G)\pmod P$라고 바꿔 생각할 수 있다.

 

여기서 Sqaure root decomposition + Meet in the middle(이하 MITM)의 아이디어가 들어간다.

어떤 자연수 $m$에 대해 $f=F^m$이라고 하면, $f^{\left \lfloor \frac n m \right \rfloor}(S)\equiv g^{n\mod m}(G)\pmod P.$

$\left \lfloor \frac n m \right \rfloor \le \left \lfloor \frac P m \right \rfloor $이므로 $\left \lfloor \frac P m \right \rfloor+m$번의 연산으로 $f^{\left \lfloor \frac n m \right \rfloor}(S)$와 $g^{n\mod m}(G)$로 가능한 모든 경우를 찾을 수 있다.

 

이 때, $m=\left \lfloor \sqrt P \right \rfloor$로 정하면 전체 시간 복잡도가 최적에 가까워질 것이다.

MITM을 위해 set을 사용할 시 로그가 붙는데, 큰 의미는 없다.

 

본격적으로 코딩을 위해 $f$와 $g$를 구하자.

• $f(x)=F^m(x)=A^mx+B\cdot (A^m-1) \cdot \mathrm{inv}_P(A-1).$
• $g(x)=F^{-1}(x)=\mathrm{inv}_P(A)x-B\cdot \mathrm{inv}_P(A).$

보이다시피 $A\neq 0,1$이다. 이 경우는 따로 구해주면 된다.

함수 $\alpha(x)=ax+b, \beta(x)=cx+d$에 대해 $\alpha \circ \beta (x)=acx+ad+b$가 된다는 것을 참고하자.

 

#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define all(x) (x).begin(), (x).end()
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)

ll P, A, B, S, G;
#define Add(x,y) x = add(x,y)
#define Mul(x,y) x = mul(x,y)
ll add(ll x, ll y) { return (x=(x+y)%P) >= 0 ? x : x+P; }
ll mul(ll x, ll y) { return (x=(x*y)%P) >= 0 ? x : x+P; }
ll pw(ll x, ll e) {
    ll r = 1;
    while (e > 0) {
        if (e%2) r = mul(r,x);
        e /= 2, x = mul(x,x);
    }
    return r;
}
ll inv(ll x) { return pw(x,P-2); }

int main() {
    int t; scanf("%d", &t); while (t-- > 0)
    {
        scanf("%lld %lld %lld %lld %lld", &P, &A, &B, &S, &G);
        A %= P, B %= P, S %= P, G %= P;
        if (A == 0) {
            if (S == G) puts("0");
            else if (B == G) puts("1");
            else puts("-1");
            continue;
        } else if (A == 1) {
            if (B == 0) {
                if (S == G) puts("0");
                else puts("-1");
            }
            else printf("%lld\n",mul(G-S,inv(B)));
            continue;
        }
        vector<ll> f;
        map<ll,ll> g;
        ll m = sqrt(P);
        {
            ll c1 = pw(A,m), c2 = mul(mul(B,pw(A,m)-1),inv(A-1));
            rep(i,0,P/m) {
                f.push_back(S);
                S = add(mul(c1,S),c2);
            }
        }
        {
            ll c1 = inv(A), c2 = mul(-B,inv(A));
            rep(i,0,m-1) {
                if (!g.count(G)) g[G] = i;
                G = add(mul(c1,G),c2);
            }
        }
        bool found = false;
        rep(i,0,P/m) {
            if (g.count(f[i])) {
                printf("%lld\n", i*m+g[f[i]]);
                found = true;
                break;
            }
        }
        if (not found) puts("-1");
    }
}

이산 로그를 이용한 풀이

식을 $n$에 관해서 정리하면 $n=\log _A\left (\frac {(A-1)G+B}{(A-1)S+B}\right )$가 된다.

#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define all(x) (x).begin(), (x).end()
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)

ll P, A, B, S, G;
#define Add(x,y) x = add(x,y)
#define Mul(x,y) x = mul(x,y)
ll add(ll x, ll y) { return (x=(x+y)%P) >= 0 ? x : x+P; }
ll mul(ll x, ll y) { return (x=(x*y)%P) >= 0 ? x : x+P; }
ll pw(ll x, ll e) {
    ll r = 1;
    while (e > 0) {
        if (e%2) r = mul(r,x);
        e /= 2, x = mul(x,x);
    }
    return r;
}
ll inv(ll x) { return pw(x,P-2); }

ll dlog(ll a, ll b) {
    if (b == 1) return 0;
    if (a == b) return 1;
    if (a <= 1) return -1;
    ll m = sqrt(P);
    map<ll,ll> g;
    rep(i,0,m-1) {
        if (!g.count(b)) g[b] = i;
        Mul(b,inv(a));
    }
    rep(i,0,P/m) {
        if (g.count(pw(a,i*m))) {
            return i*m+g[pw(a,i*m)];
        }
    }
    return -1;
}

int main() {
    int t; scanf("%d", &t); while (t-- > 0)
    {
        scanf("%lld %lld %lld %lld %lld", &P, &A, &B, &S, &G);
        A %= P, B %= P, S %= P, G %= P;
        if (add(mul(A,S),B) == S) {
            if (S == G) puts("0");
            else puts("-1");
            continue;
        }
        if (A == 1) { // B!=0
            printf("%lld\n",mul(G-S,inv(B)));
            continue;
        }
        ll t = mul(add(mul(A-1,G),B), inv(add(mul(A-1,S),B)));
        printf("%lld\n", dlog(A,t));
    }
}