13. Anniversary

本文主要是介绍13. Anniversary，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：Anniversary

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

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

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

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

#include <bits/stdc++.h>
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();}
}

这篇关于13. Anniversary的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---