TIOJ 1695：Problem E 移動週期問題

TIOJ 1695：Problem E 移動週期問題

題目大意：給 $n$ 跟 $m$，問從 $1$ 開始，每次 $\times n\ \text{mod}\ m$，循環之前的長度以及循環節的長度。

解法：我原本以為循環節長度會是 $φ(\frac{m}{gcd(n,m)})$ 的因數，然後去二分搜循環前的長度，結果一直 $\text{WA}$，在問過 8e7 後，才知道循環節長度應該是 $lcm(f(p_1^{c_1}),f(p_2^{c_2}),...,f(p_k^{c_k}))$，其中 $f(x)$ 是在模 $x$ 下的循環節長度，8e7orz。可以知道循環前長度是每個質因數循環前長度的最大值，然後如果現在看到的質因數與 $n$ 互質，則循環前長度是 $0$，循環節長度是 $φ(p_i^{c_i})$ 的因數；如果不互質，循環前長度可以直接找，循環節長度則是 $1$。在乘法的時候因為有可能模一個 $\text{long long}$ 的數，所以要用 $\text{__int128}$。

$\text{Code：}$

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

#define Waimai ios::sync_with_stdio(false),cin.tie(0)
#define FOR(x,a,b) for(int x=a;x<=b;x++)
#define pb emplace_back
#define F first
#define S second

const int MAX = 1e7;

bitset < MAX + 5 > isp;
vector<int> prime;

long long n, mod, mx, ans;
vector<long long> factor;
vector<pair<int, int>> prime_factor;

void init() {
    FOR (i, 2, MAX) {
        if (!isp[i]) {
            prime.pb (i);
            if (1ll * i * i <= MAX) {
                for (int j = i * i; j <= MAX; j += i) {
                    isp[j] = 1;
                }
            }
        }
    }
}
long long lcm (long long x, long long y) {
    return x / __gcd (x, y) * y;
}
void dfs (int pos, long long now) {
    if (pos == prime_factor.size()) {
        factor.pb (now);
        return;
    }
    FOR (i, 0, prime_factor[pos].S) {
        dfs (pos + 1, now);
        now *= prime_factor[pos].F;
    }
}
void get_factor (int p, int cnt) {
    factor.clear();
    prime_factor.clear();
    prime_factor.pb (p, cnt - 1);
    int x = p - 1;
    for (int i = 0, I = min (MAX, (int) sqrt (x)); i < prime.size() && prime[i] <= I && x > 1; i++) {
        int pp = prime[i];
        if (x % pp == 0) {
            int c = 0;
            while (x % pp == 0) {
                x /= pp;
                c++;
            }
            prime_factor.pb (pp, c);
        }
    }
    if (x > 1) {
        prime_factor.pb (x, 1);
    }
    dfs (0, 1);
    sort (factor.begin(), factor.end());
    factor.erase (unique (factor.begin(), factor.end()), factor.end());
}
long long power (long long d, long long up, long long m) {
    long long A = 1;
    while (up) {
        if (up & 1) {
            A = (__int128) A * d % m;
        }
        d = (__int128) d * d % m;
        up >>= 1;
    }
    return A;
}
void cal (int p, int cnt, long long tot) {
    if (n % p == 0) {
        int c = 0;
        long long now = 1;
        while (now != 0) {
            c++;
            now = (__int128) now * n % tot;
        }
        mx = max (mx, 1ll * c);
        return;
    }
    get_factor (p, cnt);
    for (long long f : factor) {
        if (power (n, f, tot) == 1) {
            ans = lcm (ans, f);
            return;
        }
    }
}

void solve() {
    if (mod == 1) {
        cout << "0 1\n";
        return;
    }
    mx = 0, ans = 1;
    long long tmp = mod;
    for (int i = 0; i < prime.size() && tmp > 1; i++) {
        int p = prime[i];
        if (tmp % p == 0) {
            int cnt = 0;
            long long tot = 1;
            while (tmp % p == 0) {
                tmp /= p;
                cnt++;
                tot *= p;
            }
            cal (p, cnt, tot);
        }
    }
    cout << mx << ' ' << ans << '\n';
}

int main() {
    Waimai;
    init();
    while (cin >> n >> mod) {
        solve();
    }
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！