Zerojudge e450：電石爬樓梯

Zerojudge e450：電石爬樓梯

題目大意：給一個數字 $n$ ，第 $i$ 行輸出費式數列對 $i$ 取餘數的週期。

解法：我是看討論區的解法解的 (聽說他資奧金牌)，會用到質數、矩陣快速冪。

$\text{Code：}$

#pragma GCC optimize("O3")
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <memory.h>
#define LL long long
#define int long long
#define F first
#define S second
using namespace std;

LL len[3000500] = {0};
LL p[269] = {2};
int t;
pair<int, int> pp[100];
int all[5000], pos;

void p_init() {
    int now = 1;
    for (int i = 3; i < 1732; i++) {
        bool is = 1;
        for (int j = 0; j < now; j++)
            if (i % p[j] == 0) {
                is = 0;
                break;
            }
        if (is)
            p[now++] = i;
    }
}

struct mat {
    LL num[2][2];
    void init (LL a, LL b, LL c, LL d) {
        num[0][0] = a;
        num[0][1] = b;
        num[1][0] = c;
        num[1][1] = d;
    } void mult (mat m, LL mod) {
        mat temp = *this;
        for (int i = 0; i < 2; i++)
            for (int j = 0; j < 2; j++)
                this->num[i][j] = (temp.num[i][0] * m.num[0][j] + temp.num[i][1] * m.num[1][j]) % mod;
    }
};

bool mat_power (LL n, LL mod) {
    mat ans, temp;
    ans.init (1, 0, 0, 1), temp.init (1, 1, 1, 0);
    while (n) {
        if (n & 1)
            ans.mult (temp, mod);
        n >>= 1;
        temp.mult (temp, mod);
    }
    if (ans.num[0][0] == 1 && ans.num[0][1] == 0 && ans.num[1][0] == 0 && ans.num[1][1] == 1)
        return 1;
    return 0;
}

void getall (int nownum, int nowpos) {
    if (pp[nowpos].F == 0) {
        all[pos++] = nownum;
        return;
    }
    for (int i = 0; i <= pp[nowpos].S; i++) {
        getall (nownum, nowpos + 1);
        nownum *= pp[nowpos].F;
    }
}

int getin (int x) {
    int now = -1;
    for (int i = 0; i < 7; i++)
        pp[i].F = pp[i].S = 0;
    for (int i = 0; i < 269; i++) {
        if (x == 1)
            break;
        if (x % p[i])
            continue;
        now++;
        pp[now].F = p[i];
        while (x % p[i] == 0) {
            pp[now].S++;
            x /= p[i];
        }
    }
    if (x != 1)
        pp[now + 1].F = x, pp[now + 1].S = 1;
    memset (all, 0, sizeof (all)), pos = 0;
    getall (1, 0);
    sort (all, all + pos);
}

void test (int pr, int x, bool is19) {
    getin (x);
    if (is19 == 0) {
        for (int i = 1; i < pos; i++) {
            if (mat_power (all[i], pr)) {
                len[pr] = all[i];
                return;
            }
        }
    } else {
        for (int i = 1; i < pos; i++) {
            if (x / all[i] % 2 == 0)
                continue;
            if (mat_power (all[i], pr)) {
                len[pr] = all[i];
                return;
            }
        }
    }
}

void pis (int pr) {
    if (pr % 10 == 1 || pr % 10 == 9)
        test (pr, pr - 1, 0);

    else
        test (pr, 2 * (pr + 1), 1);
}

void getpk (LL pr, LL now, int num) {
    if (now > t)
        return;
    if (num == 1)
        pis (pr);
    else
        len[now] = now / pr * len[pr];
    getpk (pr, now * pr, num + 1);
}

void ppk() {
    for (int i = 0; i < 269; i++) {
        if (p[i] == 2 || p[i] == 5)
            getpk (p[i], p[i]*p[i], 2);
        else
            getpk (p[i], p[i], 1);
    }
}

void np (int total, int nowp, int nowpos) {
    if (total > t)
        return;
    if (len[total] == 0)
        len[total] = len[nowp] * len[total / nowp] / __gcd (len[nowp], len[total / nowp]);
    np (total * p[nowpos], nowp * p[nowpos], nowpos);
    for (int i = nowpos + 1; i < 269; i++)
        np (total * p[i], p[i], i);
}

void solve() {
    len[1] = 1, len[2] = 3, len[5] = 20;
    ppk();
    for (int i = 0; i < 269; i++)
        np (p[i], p[i], i);
}

void check (int x) {
    bool is = 0;
    int sum = 1, y = x;
    for (int i = 0; i < 269; i++) {
        if (is == 1)
            break;
        while (x % p[i] == 0) {
            sum *= p[i];
            x /= p[i];
            is = 1;
        }
    }
    if (is == 0)
        pis (x);
    else
        len[y] = len[sum] * len[x] / __gcd (len[sum], len[x]);
}

signed main() {
    p_init();
    scanf ("%lld", &t);
    solve();
    for (int i = 1; i <= t; i++) {
        if (len[i] == 0)
            check (i);
        printf ("%lld\n", len[i]);
    }
}

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