P8377 [PFOI Round1] 暴龙的火锅

记录74

#include<bits/stdc++.h> using namespace std; int a[1000010]; int main(){ //数根定理或 "弃九法" int T,n; a[1]=a[2]=1; for(int i=3;i<=1000000;i++) a[i]=(a[i-1]+a[i-2])%9; for(int i=1;i<=1000000;i++) a[i]=(a[i-1]+a[i])%9; cin>>T; while(T--){ cin>>n; cout<<a[n]<<endl; } return 0; }

题目传送门https://www.luogu.com.cn/problem/P8377

突破口

定义 S(x) 表示 x 的每一位的数字之和，例如：S(14)=1+4=5，S(114514)=1+1+4+5+1+4=16.

另外，定义 fib(x) 代表斐波那契数列的第 x 项，具体地：

fib(1)=fib(2)=1, fib(x)=fib(x−1)+fib(x−2) (x≥3).

现在给定 n，求出下式的值，其中 mod9 表示对 9 取余数：

(S(fib(1))+S(fib(2))+S(fib(3))+...+S(fib(n)))mod9.

思路

给定 n，计算：

(S(fib(1))+S(fib(2))+⋯+S(fib(n)))mod9
其中：
S(x) 是 x 的各位数字之和
fib(1)=fib(2)=1，fib(x)=fib(x-1)+fib(x-2)
🔑核心数学知识：数根（Digital Root）与模 9 性质
关键定理：
对任意正整数 x，有：

一个数与其各位数字之和在模 9 意义下同余

✅ 举例：
S(13) = 1+3 = 4，13 % 9 = 4
S(114514) = 16，114514 % 9 = 1+1+4+5+1+4 = 16 → 1+6=7，而 114514 ÷ 9 = 12723*9 + 7 → 余 7
⚠️ 注意：当 x % 9 == 0 且 x ≠ 0 时，S(x) % 9 == 0（如 x=9, 18, 99）

因此：

S(fib(i))mod9=fib(i)mod9

🎯问题转化
现在问题变成：
求斐波那契数列前 n 项和 mod 9
而我们知道：
斐波那契数列模 9 会周期性循环（皮萨诺周期 Pisano Period）
但本题 n ≤ 1e6（从数组大小 a[1000010] 可知），直接预处理即可

符号≡读作“同余于”，是数论（Number Theory）中的核心符号，用于表示两个数在模某个整数下“余数相同”。

---

✅ 定义

我们说：

a ≡ b (mod m)
读作：“a 同余于 b 模 m”

当且仅当：

m 整除 (a − b)，即(a − b) % m == 0

换句话说：

a 和 b 除以 m 的余数相同

---

🌰 举个例子

• 17 ≡ 5 (mod 12)
  因为17 ÷ 12 = 1 余 5，5 ÷ 12 = 0 余 5→ 余数都是 5 ✅

• 25 ≡ 1 (mod 6)
  因为25 − 1 = 24，而24 ÷ 6 = 4（整除）✅

• 10 ≡ 1 (mod 9)
  因为10 − 1 = 9，能被 9 整除 → 这就是“弃九法”的基础！

代码简析

#include<bits/stdc++.h> using namespace std; int a[1000010];

• 定义全局数组a，大小 1e6+10，用于预处理

int main(){ int T, n;

• 声明变量

🔥 第一步：计算 fib(i) mod 9

a[1] = a[2] = 1; for(int i = 3; i <= 1000000; i++) a[i] = (a[i-1] + a[i-2]) % 9;

• 此时a[i] = fib(i) % 9
• 利用递推公式，每一步都 mod 9，防止溢出且保持正确性

✅ 因为(A + B) mod 9 = ((A mod 9) + (B mod 9)) mod 9

🔥 第二步：计算前缀和 mod 9

for(int i = 1; i <= 1000000; i++) a[i] = (a[i-1] + a[i]) % 9;

• 现在a[i] = (fib(1) + fib(2) + ... + fib(i)) % 9
• 这正是我们需要的答案！

💡 注意：这里复用了数组a，先存 fib(i)%9，再覆盖为前缀和%9

🔥 第三步：回答询问

cin >> T; while(T--){ cin >> n; cout << a[n] << endl; } return 0; }

• 直接输出预处理好的a[n]

🧪 样例验证（n=7）

→ 输出6✅ 与样例一致！

注意：S(fib(7)) = S(13) = 4，而13 % 9 = 4，所以用fib(7)%9代替S(fib(7))是正确的。

❓ 为什么可以这样替换？

因为题目最终要求的是总和 mod 9

这是由S(x) ≡ x (mod 9)的线性性质决定的。

✅ 即使中间某项S(fib(i))比fib(i)%9大（比如fib(i)=13,S=4,13%9=4），它们在 mod 9 下相等，总和也相等。

⚠️ 边界情况：fib(i) = 0？

• fib(i)永远 ≥1（i≥1），所以不会出现x=0的特殊情况
• S(x) % 9 == x % 9对所有x ≥ 1成立

✅ 总结：代码正确性依赖两大支柱

通过这两点，代码将一个看似需要高精度计算的问题，转化为简单的模 9 递推 + 前缀和，高效且正确。

📌 补充：为什么数组开到 1e6？

• 题目中最大n可能达到114514（样例中有），而1e6 > 114514
• 所以预处理到1e6足够覆盖所有可能输入

✅ 最终结论

利用了“弃九法”（数根性质），将复杂的数字和问题简化为模 9 下的斐波那契前缀和，是数学优化 + 预处理竞赛技巧

补充

🌟 一句话理解“弃九法”

一个数除以 9 的余数，等于它各位数字之和除以 9 的余数。

例如：

• 123→1+2+3 = 6→123 ÷ 9 = 13×9 + 6→ 余 6 ✅
• 999→9+9+9 = 27 → 2+7=9→999 ÷ 9 = 111→ 余 0，而9 ≡ 0 (mod 9)✅

这就是为什么它叫“弃九法”——你可以不断把数字加起来，直到剩一位（数根），它就告诉你原数 mod 9 是多少（如果是 9，就代表余 0）。

🔍 为什么成立？——从十进制展开说起

任何一个十进制数，比如528，其实可以写成：

528=5×100+2×10+8×1=5×10^2+2×10^1+8×10^0

一般地，一个数 x=dkd(k-1)…d1d0（ di是各位数字）可表示为：

x=d0+d1⋅10+d2⋅10^2+⋯+dk⋅10^k

现在关键来了：10 对 9 取模是多少？

10≡1(mod9)

所以：

10^2=10⋅10≡1⋅1=1(mod9)

10^3≡1(mod9)

⋮

10^n≡1(mod9)

于是：

x=d0+d1⋅10+d2⋅102+⋯≡d0+d1⋅1+d2⋅1+⋯(mod9)

即：

x≡d0+d1+d2+⋯(mod9)

而右边就是各位数字之和 S(x)S(x)！

✅ 所以：

x≡S(x)(mod9)x≡S(x)(mod9)

这就证明了“弃九法”！

🧠 举个生活化例子

想象你有一堆硬币，每9 枚可以换成一张“9元券”，最后剩下的就是余数。

现在，数字10其实就相当于 “1 个十元 + 0 个一元”。
但因为10 = 9 + 1，所以“10元”其实等价于“1元”（多出的 9 元被换掉了）。

同理：

• 100 = 99 + 1 = 11×9 + 1→ 等价于 1
• 1000 = 999 + 1→ 也等价于 1

所以，每一位的“权重”（1, 10, 100, 1000...）在 mod 9 下都等于 1！

因此，整个数的大小，就只取决于“有多少个 1 被加起来”——也就是各位数字之和。

⚠️ 特殊情况：余数为 0

• 如果一个数能被 9 整除（如 18, 99, 1233），那么它的数字和也是 9 的倍数。
• 比如S(99) = 18 → 1+8=9，而9 ≡ 0 (mod 9)
• 所以：当数字和是 9 的倍数时，原数 ≡ 0 (mod 9)

💡 数根（反复求数字和直到一位数）的结果：

• 如果是 9 → 原数 ≡ 0 (mod 9)
• 否则 → 数根 = 原数 mod 9

✅ 总结（通俗版）

• 因为10 ≡ 1 (mod 9)，所以10 的任何次方也 ≡ 1
• 所以一个数abc（即a×100 + b×10 + c）在 mod 9 下就等于a + b + c
• 这就是“弃九法”的数学根源！
• 它让我们可以用简单的加法，快速判断一个大数除以 9 的余数

这个原理不仅用于验算加减乘法（古代商人常用），也在编程竞赛中频繁出现！