user

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
三阶斐波那契数的非约数

序列1, 1, 1, 3, 5, 9, 17, 31, 57, 105, 193, 355, 653, 1201 …
的定义为T1 = T2 = T3 = 1以及Tn = Tn-1 + Tn-2 + Tn-3。

可以说明，27不能整除这个序列中的任何一项。事实上，27是第一个拥有这一性质的奇数。

求第124个不能整除上述序列中任何一项的奇数。

我有一个不确定的思路:直接检查.
首先整除序列某一项即为模意义下为0,暴力递推的时候检查这个即可.

陷入循环的判定为出现前面出现过的三元组,可以用哈希a+b*mod+c*mod^2然后检查.

检查一个数字的复杂度是O(n^3).

请给我c++代码实现,注意只检查27往后的奇数.


gpt

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
你的思路本质上是**对的，而且在数学上也是标准做法**：
这是一个**模 m 的三阶线性递推序列是否出现 0**的问题，本质等价于在模意义下判断是否存在 (T_n \equiv 0 \pmod m)。

我先帮你**把思路理顺并稍微修正复杂度判断**，然后给你一份**可以直接跑的 C++ 实现**（只检查 27 之后的奇数，直到找到第 124 个）。

---

## 一、问题建模（确认你理解得完全正确）

定义三阶斐波那契（Tribonacci）：
[
T_1 = T_2 = T_3 = 1,\quad
T_n = T_{n-1} + T_{n-2} + T_{n-3}
]

对一个奇数 (m)，我们考虑模 (m) 的序列：
[
(T_{n-2} \bmod m,; T_{n-1} \bmod m,; T_n \bmod m)
]

### 关键事实

* 模 (m) 下，状态最多只有 (m^3) 种
* 一旦三元组重复 → 序列进入循环
* 若在进入循环前**从未出现 (T_n \equiv 0 \pmod m)**
  ⇒ (m) 不能整除该序列的任何一项

所以你的判断条件是：

> **是否在模 m 的 Tribonacci 序列中出现过 0**

---

## 二、复杂度澄清（重要）

你写的是 **O(n³)**，更准确地说是：

* **单个 m 的复杂度**：
  最坏 (O(m^3)) 次状态更新
* **m 从 27 起枚举奇数**：
  实际上远远跑不到最坏，因为大多数 m 很快就出现 0

对于本题规模，这是**完全可接受的**，而且是 OEIS / Project Euler 类问题的标准解法。

---

## 三、实现细节设计

### 状态表示

用三元组：
1
(a, b, c) = (T_{n-2} mod m, T_{n-1} mod m, T_n mod m)
1
### 哈希方式（你给的思路是对的）
1
key = a + b * m + c * m * m
1
2
3
4
5
6
7
8
### 停止条件

* 若 `c == 0` → **m 可整除某项** → 不合格
* 若状态重复 → **进入循环且未见 0** → 合格

---

## 四、完整 C++ 实现（严格按你的思路）
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
#include <bits/stdc++.h>
using namespace std;

/*
检查奇数 m 是否不能整除 Tribonacci 序列的任何一项
true  -> 不整除任何一项（合格）
false -> 存在 T_n ≡ 0 (mod m)
*/
bool check(long long m) {
    unordered_set<long long> vis;
    vis.reserve(1000000);

    long long a = 1 % m;
    long long b = 1 % m;
    long long c = 1 % m;

    while (true) {
        // 如果出现 0，则 m 可以整除某一项
        if (c == 0) return false;

        // 哈希三元组
        long long key = a + b * m + c * m * m;
        if (vis.count(key)) {
            // 状态重复，进入循环，且未出现 0
            return true;
        }
        vis.insert(key);

        long long d = (a + b + c) % m;
        a = b;
        b = c;
        c = d;
    }
}

int main() {
    int count = 0;
    long long m = 27;  // 题目要求从 27 之后开始

    while (true) {
        if (m % 2 == 1) {  // 只检查奇数
            if (check(m)) {
                count++;
                if (count == 124) {
                    cout << m << endl;
                    return 0;
                }
            }
        }
        m += 2;
    }
}
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
---

## 五、一些可选优化（不是必须）

如果你之后想跑得更快：

1. **用 bitset / vector<bool> 替代 unordered_set**

   * 空间换时间
2. **提前过滤**

   * 若 (m) 与某些小周期有公因子，几乎必定出现 0
3. **数学优化**

   * 研究 Tribonacci 在模 p 下的秩与周期（偏数论）

但对这道题来说，**上面的暴力是完全够的**。

---

## 六、总结一句话

> 这是一个典型的「模线性递推 + 状态循环检测」问题，你的思路是完全正确的，这份代码就是你思路的直接、干净实现。

如果你愿意，我也可以：

* 帮你估算大概运行时间
* 或给你一个 **带剪枝的版本**
* 或解释为什么 **27 是第一个奇数**

随时继续 👍

fun fact

这个题的127th非常奇怪,注定了不太可能是什么复杂做法,所以直接暴力就行了.