模板 & 题解 - [Luogu P4000] 斐波那契数列

发表于 更新于 分类于 ， 本文字数： 358 阅读时长 ≈ 1 分钟

题目链接

原始题面

题目描述

大家都知道，斐波那契数列是满足如下性质的一个数列:

  • \(f_1 = 1\)
  • \(f_2 = 1\)
  • \(f_n = f_{n-1} + f_{n-2}\) (\(n \geq 2\) 且 \(n\) 为整数) 请你求出 \(f_n \mod p\) 的值

输入格式

  • 第 1 行：一个整数 \(n\)
  • 第 2 行：一个整数 \(p\)

输出格式

  • 第 1 行: \(f_n \mod p\) 的值

输入输出样例

输入 #1

1
2
5
1000000007

输出 #1

1
5

输入 #2

1
2
10
1000000007

输出 #2

1
55

说明 / 提示

对于 \(100\%\) 的数据，\(n \leq 10^{30000000}, p<2^{31}\)

解题思路

科技题

先摆个论文: The Period of the Fibonacci Sequence Modulo j

这篇论文给出了找 Fibonacci 数列和 Lucas 数列循环节的方法 (实际上所有二阶递推数列都可以这样做)

简单来说就是这样:

  • 考虑 \(p\) 的唯一分解

    \[ p=\prod_{i=1}^{\omega(p)}p_i^{\alpha_i} \]

    令 \(l(p)\) 为 \(F_n\) 模 \(p\) 的循环节，则

    \[ l(p)=\operatorname{lcm}\{l(p_1^{\alpha_1}),l(p_2^{\alpha_2}),...,l(p_{\omega(p)}^{\alpha_{\omega(p)}})\} \]

  • 对素数 \(p\), 有如下定理:

    • \[ l(p^n)\mid l(p)p^{n-1} \]
    • 若 \(\left(\frac{5}{p}\right)=1\), 即 \(p\equiv\pm 1\pmod{5}\), 则 \[ l(p)\mid p-1 \]
    • 若 \(\left(\frac{5}{p}\right)=-1\), 即 \(p\equiv\pm 2\pmod{5}\), 则 \[ l(p)\mid 2(p+1) \]

代码里还有一些别的科技，推荐看一看

复杂度

\(O(\max\{\lg n,\sqrt p\})\)

代码参考

Show code

Luogu_P4000view raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <bits/stdc++.h>
using namespace std;
using u64 = uint64_t;
using u128 = __uint128_t;
u64 p;
struct Mat {
  u128 data[2][2];
  Mat() {}
  template <typename Up>
  Mat(Up a = 0, Up b = 0, Up c = 0, Up d = 0) {
    data[0][0] = a;
    data[0][1] = b;
    data[1][0] = c;
    data[1][1] = d;
  }
  template <typename Up>
  constexpr Mat &operator=(Up &&rhs) noexcept {
    (*this)(0, 0) = forward<Mat>(rhs)(0, 0);
    (*this)(0, 1) = forward<Mat>(rhs)(0, 1);
    (*this)(1, 0) = forward<Mat>(rhs)(1, 0);
    (*this)(1, 1) = forward<Mat>(rhs)(1, 1);
    return *this;
  }
  constexpr u128 &operator()(size_t x, size_t y) noexcept {
    return this->data[x][y];
  }
  Mat operator*(Mat &rhs) noexcept {
    return Mat(
      ((*this)(0, 0) * rhs(0, 0) % p + (*this)(0, 1) * rhs(1, 0) % p) % p,
      ((*this)(0, 0) * rhs(0, 1) % p + (*this)(0, 1) * rhs(1, 1) % p) % p,
      ((*this)(1, 0) * rhs(0, 0) % p + (*this)(1, 1) * rhs(1, 0) % p) % p,
      ((*this)(1, 0) * rhs(0, 1) % p + (*this)(1, 1) * rhs(1, 1) % p) % p);
  }
};
constexpr uint64_t dec2uint_mod(const char * const num,
                                const uint64_t mod = UINT64_MAX) {
  size_t len = strlen(num);
  u128 ans = 0;
  for (auto pch = num; pch < num + len;)
    (((ans *= 10) %= mod) += *(pch++) & 0x0F) %= mod;
  return ans;
}
u64 period(u64 p) {
  auto g = [](u64 p) -> u64 {
    static const u64 _[6] = {0, 1, 3, 8, 6, 20};
    if (p <= 5) return _[p];
    return (p % 5 == 1 || p % 5 == 4) ? (p - 1) : ((p + 1) * 2);
  };
  auto gcd = [](u64 n, u64 m) {
    while (m ^= n ^= m ^= n %= m);
    return n;
  };
  u64 res = 1;
  for (u128 i = 2; i * i <= p; ++i)
    if (p % i == 0) {
      p /= i;
      u64 x = g(i), _ = p;
      while (p % i == 0) p /= i;
      x *= _ / p;
      res = res / gcd(res, x) * x;
    }
  if (p > 1) {
    u64 x = g(p);
    res = res / gcd(res, x) * x;
  }
  return res;
}
void solve() {
  string s;
  cin >> s >> p;
  if (p < 2) {
    cout << '0';
    return;
  }
  cout << [](Mat a, u64 b) -> u64 {
    Mat res(1, 0, 0, 1);
    for (; b; b >>= 1, a = a * a)
      if (b & 1) res = res * a;
    return (u64)res(0, 1);
  }({1, 1, 1, 0}, dec2uint_mod(s.c_str(), period(p)));
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  solve();
  return 0;
}