循環節（cycle）/ 循環入口（cycle entry）筆記（以 ZeroJudge e864 循環小數為例）
0) 題目模型：為什麼會循環？「狀態」是誰？
e864 的小數展開其實就是長除法反覆做同一件事。若目前餘數為 r（0 <= r < B）：
- 下一位數字：
d = (r * 10) / B - 新餘數：
r' = (r * 10) % B
因此序列的「狀態」就是餘數 r，轉移函式是 f(r) = (r*10) % B。
重點觀察（只講怎麼做，不講證明）：
- 餘數最多只有 B 種
- 一旦某個餘數重複出現，之後產生的小數位會開始重複
- r == 0 代表小數終止（題目要求輸出 (0)）
1) 名詞：循環入口與循環節在這題代表什麼？
- 循環入口（cycle entry）：第一次遇到「重複餘數」時，那個餘數所對應的小數位置（括號開始的位置）
- 循環節（cycle）：從入口開始，到下一次回到同一個入口餘數之間產生的那段小數位（括號內內容）
- tail 長度 μ：括號前的小數位長度
- cycle 長度 λ：括號內循環節長度
2) 統一範例：用 678(1234) 講清楚入口與循環節（概念對齊）
678(1234) 表示序列：
6 → 7 → 8 → 1 → 2 → 3 → 4 → 1 → 2 → 3 → 4 → ...
- 循環入口 =
1 - 循環節 =
1 → 2 → 3 → 4 - μ = 3（6 到 1 走 3 步）
- λ = 4（循環節長度）
接下來每個方法都用 678(1234) 示範「如何求入口」與「如何求循環節」。
3) e864 的輸出需求對應到入口/循環節
- 括號
(從「入口位置」開始 - 括號
)結束前是「循環節內容」 - 若無循環（餘數變 0）：輸出
(0) - 若循環節長度 > 50：括號內只印前 50 位再加
...
Part 1：用 set 判斷重複（O(k log k), O(k)）
適合：最直覺、狀態可比較排序、資料不大。
入口（cycle entry）怎麼求？
做法：
1. 用 set 存已出現的狀態
2. 從起點一路走：
- 如果下一個狀態已在 set：該狀態就是入口（第一次再次遇到的狀態）
- 否則插入並繼續
用 678(1234)：
- seen 依序加入：6,7,8,1,2,3,4
- 下一步回到 1，發現 1 已存在
- 入口 = 1
循環節（cycle）怎麼求？
set 只能告訴你「重複了」，要取出循環節內容，常見補法：
- 已知入口 1 後，從 1 開始一直走到再次回到 1，沿途收集就是循環節
用 678(1234)：
- 1 → 2 → 3 → 4 → 1（回來停止）
- 循環節 = 1234，λ = 4
Part 2：用 unordered_map（或陣列）記「第一次出現位置」（平均 O(k), O(k)）
適合：競賽最推薦。入口位置、循環節長度、循環內容都能一次拿到。
入口（cycle entry）怎麼求？
用 first[state] = step 記錄「第一次看到 state 的步數」：
- 當你走到某個 state，發現它已存在於 first：
- 入口 = 這個 state
- μ = first[state]
用 678(1234)：
- step0: 6（first[6]=0）
- step1: 7（first[7]=1）
- step2: 8（first[8]=2）
- step3: 1（first[1]=3）
- step4: 2（first[2]=4）
- step5: 3（first[3]=5）
- step6: 4（first[4]=6）
- step7: 1（已出現過，first[1]=3）
- 入口 = 1，μ = 3
循環節（cycle）怎麼求？
- λ = step - first[entry]
- 循環節內容：從 entry 第一次出現的位置開始，取長度 λ 的那段
用 678(1234)：
- λ = 7 - 3 = 4
- 循環節 = 從 step3 開始 4 個：1,2,3,4
Part3：Floyd 龜兔賽跑（O(k), O(1)）
適合：不想存 seen，記憶體要省到 O(1)。
入口（cycle entry）怎麼求？
Phase 1：先在環內相遇
- A 慢：一次走 1 步
- B 快：一次走 2 步
- 相遇點一定在環內（不一定是入口）
Phase 2：找入口
- A 重設回起點
- B 留在相遇點
- A、B 都一次走 1 步
- 下一次相遇點就是入口
用 678(1234)（列出你圖那種走位感）：
Phase 1（相遇）：
| 回合 | A | B |
|---|---|---|
| 0 | 6 | 6 |
| 1 | 7 | 8 |
| 2 | 8 | 2 |
| 3 | 1 | 4 |
| 4 | 2 | 2 ← 相遇 |
相遇在 2（不是入口）。
Phase 2（找入口）：
| 步數 | A（重設） | B（留在相遇） |
|---|---|---|
| 0 | 6 | 2 |
| 1 | 7 | 3 |
| 2 | 8 | 4 |
| 3 | 1 | 1 ← 入口 |
入口 = 1。
循環節（cycle）怎麼求？
Floyd Phase 2 只給入口；要循環節內容通常再做：
- 從入口開始走，直到回到入口，沿途就是循環節
用 678(1234)：
- 1 → 2 → 3 → 4 → 1
- 循環節 = 1234，λ = 4
Part4：Floyd 先求 λ，再「錯開 λ 步」找入口（O(k), O(1)）— 詳細版
適合：你想把「入口」與「循環節長度」拆得很乾淨，流程也很直覺。
Step A：先找相遇點 meet
同 Part3 的 Phase 1。
在 678(1234) 中，meet = 2。
Step B：由 meet 求循環長度 λ
做法：
- 固定 meet
- 從 meet 開始一直走，直到再次回到 meet
- 走的步數就是 λ
用 678(1234)（從 meet=2）：
- 2 → 3（1）
- 3 → 4（2）
- 4 → 1（3）
- 1 → 2（4）回到 2
所以 λ = 4。
Step C：錯開 λ 步找入口（最直覺的入口定位）
做法：
1. p1 = 起點
2. p2 = 起點
3. p2 先走 λ 步（拉開一整圈距離）
4. p1、p2 同速走，第一次相遇就是入口
用 678(1234)：
- p1=6，p2=6
- p2 先走 4 步：6→7→8→1→2，所以 p2=2
- 同速走：
- (6,2) → (7,3) → (8,4) → (1,1)
- 入口 = 1，且走了 3 步所以 μ = 3。
循環節（cycle）怎麼求？
入口與 λ 都有了：
- 從入口走 λ 步收集：1,2,3,4
- 循環節 = 1234
Part5：Brent（O(k), O(1)）— 詳細版
適合：f() 很貴、想少做函式呼叫次數。Brent 會先求 λ，再求 μ/入口，最後循環節直接列出。
Step A：Brent 求 λ（循環長度）
概念：分段倍增比對（power = 1,2,4,8,…）
- tortoise 固定在「某段起點」
- hare 往前走並計 lam
- 每當 lam 跑滿 power，就把 tortoise 推進到 hare，power 倍增，lam 歸零再比下一段
流程（口語化）：
1. power=1, lam=1
2. tortoise = 起點
3. hare = 下一步
4. while tortoise != hare:
- 若 power == lam：tortoise = hare，power *= 2，lam=0
- hare 往前一步，lam++
用 678(1234) 直覺理解：
- hare 會一路往前跑
- tortoise 會在 1、2、4… 這些倍增檢查點更新
- 最後第一次讓 tortoise == hare 時，lam 就是 λ
此例會得到 λ = 4（因為環是 1234）。
Step B：用 λ 求 μ 與入口（錯開 λ 步）
拿到 λ 後，入口求法與 Part4 Step C 相同：
- p1 = 起點
- p2 = 起點
- p2 先走 λ 步
- 同速走到相遇：相遇點是入口，相遇前走的步數是 μ
用 678(1234)：
- λ=4
- p2 先走 4 步：6→7→8→1→2（p2=2）
- 同速走：
- (6,2) → (7,3) → (8,4) → (1,1)
- 入口 = 1，μ = 3
Step C：循環節（cycle）怎麼求？
入口與 λ 都有了：
- 從入口走 λ 步：1,2,3,4
- 循環節 = 1234
本題（e864）角度的選法比較
| 方法 | entry 好不好拿 | cycle 內容好不好拿 | 實作直覺度 | e864 推薦 |
|---|---|---|---|---|
| Part 1 set | 好拿（第一次重複） | 需要再走一圈收集 | 高 | 中 |
| Part 2 unordered_map/陣列 pos | 最好拿（位置直接有） | 最好拿（切字串） | 最高 | 最高 |
| Part3 Floyd | 可拿（Phase2） | 需額外再走一圈收集 | 中 | 中（不如 Part 2 快） |
| Part4 Floyd + λ + 錯開 | 最乾淨（μ、λ 都有） | 很好拿 | 中～偏高 | 中高 |
| Part5 Brent + λ/μ | 很乾淨（μ、λ 都有） | 很好拿 | 中（概念較多） | 中（偏進階） |
例題1 j057. 11634 - Generate random numbers
Part 1 set AC (4ms, 340KB)
#include <bits/stdc++.h>
using namespace std;
#define int long long
string next_s(string s){
int a2=stoi(s);
a2*=a2;
string ns=to_string(a2);
while(ns.size()!=8){
ns='0'+ns;
}
ns=ns.substr(2,4);
return ns;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
// stringstream cin(R"(5555
//0815
//6239
//0
//)");
string s;
while(cin>>s && s!="0"){
set<string>se;
se.insert(s);
int ans=1;
while(1){
s=next_s(s);
if (!se.insert(s).second) break;
ans++;
}
cout<<ans<<"\n";
}
return 0;
}
Part 3 龜兔賽跑 AC (6ms, 336KB)
#include <bits/stdc++.h>
using namespace std;
string next_s(string s){
long long a2 = stoll(s);
a2 *= a2;
string ns = to_string(a2);
while (ns.size() < 8) ns = '0' + ns; // 用 <8 較安全
return ns.substr(2, 4);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
// stringstream cin(R"(5555
//0815
//6239
//0
//)");
string s;
while (cin >> s && s != "0") {
// Phase 1: 找相遇點
string slow = next_s(s);
string fast = next_s(next_s(s));
while (slow != fast) {
slow = next_s(slow);
fast = next_s(next_s(fast));
}
// Phase 2: 找 μ（入口）
long long mu = 0;
slow = s;
while (slow != fast) {
slow = next_s(slow);
fast = next_s(fast); // ✅ 這裡只能走一步
mu++;
}
// 現在 slow==fast==入口
// Phase 3: 找 λ（循環長度）
long long lambda = 1;
fast = next_s(slow);
while (fast != slow) {
fast = next_s(fast);
lambda++;
}
cout << (mu + lambda) << "\n"; // 不同值總數（含 a0）
}
return 0;
}
例題2 e864. Q3-2 循環小數
Part 2 unordered_map AC (1ms, 328KB)
#include <bits/stdc++.h>
using namespace std;
int m;
int nextn(int n) {
return (n * 10) % m;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int w;
cin >> w;
while (w--) {
int n;
cin >> n >> m;
cout << n / m << '.';
n = n % m;
unordered_map<int, int> mp;
int it = 0;
int in = 0;
int L = 0;
vector<int> v;
while (1) {
if (mp.count(n)) {
in = mp[n];
L = it - in;
break;
}
mp[n] = it;
v.push_back(n * 10 / m);
n = nextn(n);
it++;
}
int size = v.size();
for (int i = 0; i < size; i++) {
if (i == in) cout << '(';
cout << v[i];
if (i - in == 50 - 1) {
cout << "...)";
break;
}
if (i - in == L - 1) {
cout << ")";
break;
}
}
cout << "\n";
}
}
Part 2 vector AC (1ms, 332KB)
#include <bits/stdc++.h>
using namespace std;
int m;
int nextn(int n) {
return (n * 10) % m;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int w;
cin >> w;
while (w--) {
int n;
cin >> n >> m;
cout << n / m << '.';
n = n % m;
vector<int> vv(m, -1);
int it = 0;
int in = 0;
int L = 0;
vector<int> v;
while (1) {
if (vv[n] != -1) {
in = vv[n];
L = it - in;
break;
}
vv[n] = it;
v.push_back(n * 10 / m);
n = nextn(n);
it++;
}
int size = v.size();
for (int i = 0; i < size; i++) {
if (i == in) cout << '(';
cout << v[i];
if (i - in == 50 - 1) {
cout << "...)";
break;
}
if (i - in == L - 1) {
cout << ")";
break;
}
}
cout << "\n";
}
}
Part 3 龜兔賽跑 AC (1ms, 332KB)
#include <bits/stdc++.h>
using namespace std;
int m;
// 狀態 n 代表「餘數 remainder」(0 <= n < m)
// 下一個餘數：n -> (n*10) % m
int nextn(int n) {
return (int)((1LL * n * 10) % m);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int w;
cin >> w;
while (w--) {
int n;
cin >> n >> m;
// 先輸出整數部分
cout << n / m << '.';
// 令 n 變成餘數，作為小數部分的起點狀態
n %= m;
int start = n; // 記住起點餘數，後面要再走一次產生輸出 digit
int in = 0; // 循環入口 (mu)
int L = 0; // 循環長度 (lambda)
// =======================
// Floyd 龜兔賽跑找循環
// 1) 先找相遇點
// =======================
int slow = nextn(start); // slow 每次走 1 步
int fast = nextn(nextn(start)); // fast 每次走 2 步
while (slow != fast) {
slow = nextn(slow);
fast = nextn(nextn(fast));
}
// =======================
// 2) 找循環入口 in (mu)
// 一個回到起點，另一個留在相遇點
// 兩者同速前進，首次相遇即入口
// =======================
in = 0;
slow = start;
while (slow != fast) {
slow = nextn(slow);
fast = nextn(fast);
in++;
}
// 此時 slow == fast == 入口餘數
// =======================
// 3) 找循環長度 L (lambda)
// 從入口再走一圈回來
// =======================
L = 1;
fast = nextn(slow);
while (slow != fast) {
fast = nextn(fast);
L++;
}
// =======================
// 產生要輸出的 digit：前綴 in 位 + 循環 min(L, 50) 位
// digit = (remainder*10)/m
// =======================
vector<int> v;
int need = in + min(L, 50);
int r = start;
for (int i = 0; i < need; i++) {
v.push_back((int)((1LL * r * 10) / m));
r = nextn(r);
}
// 依題意輸出括號與截斷
for (int i = 0; i < (int)v.size(); i++) {
if (i == in) cout << '(';
cout << v[i];
// 循環段長度 > 50：只印循環段前 50 位，結尾用 "...)"
if (L > 50 && i - in == 50 - 1) {
cout << "...)";
break;
}
// 循環段長度 <= 50：印完循環段就關括號
if (L <= 50 && i - in == L - 1) {
cout << ")";
break;
}
}
cout << "\n";
}
}
例題3 f937. 循環節
Part 2 unordered_map NA (score:66%)
查看詳細評分結果
#0: 16% AC (1ms, 316KB)
通過檢測
#1: 16% AC (4ms, 392KB)
通過檢測
#2: 17% AC (24ms, 732KB)
通過檢測
#3: 17% AC (63ms, 11.2MB)
通過檢測
#4: 17% MLE (46.9MB)
您的程式使用記憶體超過限制
#5: 17% MLE (36.8MB)
您的程式使用記憶體超過限制
#include <bits/stdc++.h>
using namespace std;
int m;
int nextn(int n) {
return (n * 10) % m;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int w;
cin >> w;
while (w--) {
int n;
cin >> n >> m;
n = n % m;
unordered_map<int, int> mp;
int it = 0;
int in = 0;
int L = 0;
while (1) {
if (mp.count(n)) {
in = mp[n];
L = it - in;
break;
}
mp[n] = it;
n = nextn(n);
it++;
}
cout << in << " " << L;
cout << "\n";
}
}
Part 2 vector NA (score:83%)
查看詳細評分結果
#0: 16% AC (1ms, 364KB)
通過檢測
#1: 16% AC (3ms, 396KB)
通過檢測
#2: 17% AC (2ms, 372KB)
通過檢測
#3: 17% AC (7ms, 1.1MB)
通過檢測
#4: 17% AC (18ms, 14.8MB)
通過檢測
#5: 17% RE (SIGABRT)
系統呼叫了 abort 函式！
terminate called after throwing an instance of 'std::bad_alloc'
what(): std::bad_alloc
Aborted (core dumped)
terminate called after throwing an instance of 'std::bad_alloc'
what(): std::bad_alloc
Aborted (core dumped)
#include <bits/stdc++.h>
using namespace std;
int m;
int nextn(int n) {
return (n * 10) % m;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int w;
cin >> w;
while (w--) {
int n;
cin >> n >> m;
n = n % m;
vector<int> vv(m, -1);
int it = 0;
int in = 0;
int L = 0;
while (1) {
if (vv[n] != -1) {
in = vv[n];
L = it - in;
break;
}
vv[n] = it;
n = nextn(n);
it++;
}
cout << in << " " << L;
cout << "\n";
}
}
Part 3 龜兔賽跑 AC (42ms, 348KB)
查看詳細評分結果
#0: 16% AC (4ms, 348KB)
通過檢測
#1: 16% AC (2ms, 320KB)
通過檢測
#2: 17% AC (8ms, 348KB)
通過檢測
#3: 17% AC (22ms, 320KB)
通過檢測
#4: 17% AC (42ms, 340KB)
通過檢測
#5: 17% AC (34ms, 324KB)
通過檢測
#include <bits/stdc++.h>
using namespace std;
int m;
// 狀態 n 代表「餘數 remainder」(0 <= n < m)
// 下一個餘數：n -> (n*10) % m
int nextn(int n) {
return (int)((1LL * n * 10) % m);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int w;
cin >> w;
while (w--) {
int n;
cin >> n >> m;
// 令 n 變成餘數，作為小數部分的起點狀態
n %= m;
int start = n; // 記住起點餘數，後面要再走一次產生輸出 digit
int in = 0; // 循環入口 (mu)
int L = 0; // 循環長度 (lambda)
// =======================
// Floyd 龜兔賽跑找循環
// 1) 先找相遇點
// =======================
int slow = nextn(start); // slow 每次走 1 步
int fast = nextn(nextn(start)); // fast 每次走 2 步
while (slow != fast) {
slow = nextn(slow);
fast = nextn(nextn(fast));
}
// =======================
// 2) 找循環入口 in (mu)
// 一個回到起點，另一個留在相遇點
// 兩者同速前進，首次相遇即入口
// =======================
in = 0;
slow = start;
while (slow != fast) {
slow = nextn(slow);
fast = nextn(fast);
in++;
}
// 此時 slow == fast == 入口餘數
// =======================
// 3) 找循環長度 L (lambda)
// 從入口再走一圈回來
// =======================
L = 1;
fast = nextn(slow);
while (slow != fast) {
fast = nextn(fast);
L++;
}
cout << in << " " << L;
cout << "\n";
}
}