CODE

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const LL INF = 1e15;

inline LL qpow(LL a, LL b, LL c) {

    LL re = 1;

    while(b) {

        if(b&1) re = re * a % c;

        a = a * a % c; b >>= 1;

    }

    return re;

}

LL gcd(LL a, LL b) { return b ? gcd(b, a%b) : a; }

void exgcd(LL a, LL b, LL &x, LL &y) {

    if(!b) { x = 1, y = 0; return; }

    exgcd(b, a%b, y, x); y -= x*(a/b);

}

int prime[100], cnt;

inline void Factor(int N) {

    cnt = 0;

    for(int i = 2; i*i <= N; ++i)

        if(N % i == 0) {

            prime[++cnt] = i;

            while(N % i == 0) N /= i;

        }

    if(N > 1) prime[++cnt] = N;

}

inline int Get_g(int p, int phi) { //找原根

    Factor(phi);

    for(int g = 2; ; ++g) {

        bool flg = true;

        for(int i = 1; i <= cnt; ++i)

            if(qpow(g, phi/prime[i], p) == 1)

                { flg = 0; break; }

        if(flg) return g;

    }

}

map<int, int>myhash;

inline LL Baby_Step_Giant_Step(LL a, LL b, LL p) {

    myhash.clear(); int m = int(sqrt(p) + 1);

    LL base = b;

    for(int i = 0; i < m; ++i) {

        myhash[base] = i;

        base = base * a % p;

    }

    base = qpow(a, m, p); LL tmp = 1;

    for(int i = 1; i <= m+1; ++i) {

        tmp = tmp * base % p;

        if(myhash.count(tmp))

            return i*m - myhash[tmp];

    }

    return -1;

}

inline LL solve(LL a, LL b, LL p, LL d, LL p_d) {

    b %= p_d;

    if(!b) return qpow(p, d-((d-1)/a+1), INF);

    LL temp = 0;

    while(b % p == 0) b /= p, ++temp, p_d /= p;

    if(temp % a) return 0;

    LL phi = p_d - p_d/p, g = Get_g(p_d, phi);

    LL ind = Baby_Step_Giant_Step(g, b, p_d);

    LL re = gcd(a, phi);

    if(ind % re) return 0;

    return re * qpow(p, temp-temp/a, INF);

}

int main() {

    int T, a, b, k;

    for(scanf("%d", &T); T; T--) {

        scanf("%d%d%d", &a, &b, &k); k = k<<1|1;

        LL ans = 1;

        for(int i = 2; i*i <= k && ans; ++i)

            if(k % i == 0) {

                int d = 0, p_d = 1;

                while(k % i == 0) k /= i, ++d, p_d *= i;

                ans *= solve(a, b, i, d, p_d);

            }

        if(k > 1 && ans) ans *= solve(a, b, k, 1, k);

        printf("%lld\n", ans);

    }

}

巴特西

BZOJ 2219 数论之神 (CRT推论+BSGS+原根指标)

CODE

最新文章

热门文章