13. Anniversary

题目链接：Anniversary

给出 \(m,l,r,k\)，让你在斐波那契数列的第 \(l\) 到第 \(r\) 项之间选出 \(k\) 个，最大化这 \(k\) 个数的 gcd，对 \(m\) 取模后输出。

首先需要知道一个重要结论：\(\gcd(F[a],F[b])=F[\gcd(a,b)]\)。

这个比较容易证明，令 \(a\lt b\)，将 \(F[b]\) 用 \(F[a]\) 和 \(F[a+1]\) 表示，像辗转相除法那样处理就好了。

现在需要在 \([l,r]\) 中选 \(k\) 个数，最大化它们的 gcd。这可以用数论分块做。求出来之后矩阵快速幂一下就可以算出相应的斐波那契数了。

#include 
using namespace std;
using ll = long long;
ll mod;
struct matrix {
    ll m[8][8];
    int sz;
    matrix() {
        memset(m, 0, sizeof(m));
        sz = 0;
    }
    void unit(int n) {
        sz = n;
        for (int i = 1; i <= n; ++i)
            m[i][i] = 1;
    }
    matrix operator*(const matrix &b) {
        matrix ans;
        for (int i = 1; i <= sz; ++i)
            for (int j = 1; j <= sz; ++j)
                for (int k = 1; k <= sz; ++k)
                    ans.m[j][k] =
                        (ans.m[j][k] + m[j][i] * b.m[i][k] % mod) % mod;
        ans.sz = sz;
        return ans;
    }
    void operator=(const matrix &b) {
        sz = b.sz;
        for (int i = 1; i <= sz; ++i)
            for (int j = 1; j <= sz; ++j)
                m[i][j] = b.m[i][j];
    }
    matrix operator^(const ll &k) {
        matrix ret, now = *this;
        ll tmp = k;
        ret.unit(this->sz);
        while (tmp) {
            if (tmp & 1)
                ret = ret * now;
            now = now * now;
            tmp >>= 1;
        }
        return ret;
    }
};

void solve() {
    ll l, r, k;
    cin >> mod >> l >> r >> k;
    ll ans = 1;
    for (ll i = 1, j; i * i <= r; ++i) {
        if (r / i - (l - 1) / i >= k)
            ans = max(ans, i);
        j = r / i;
        if (r / j - (l - 1) / j >= k)
            ans = max(ans, j);
    }
    matrix a;
    a.m[1][1] = a.m[1][2] = a.m[2][1] = 1;
    a.sz = 2;
    a = a ^ (ans - 1);
    cout << a.m[1][1] % mod << endl;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
}