自动搬运

查看原文

来自洛谷，原作者为

	chen_zhe Aya 敲可爱的~

搬运于2025-08-24 22:38:34，当前版本为作者最后更新于2022-06-06 08:02:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先要知道一个结论：一个正整数对 $9$ 取余的结果就是它各位数之和对 $9$ 取余的结果。证明如下：

一个 $n$ 位的正整数 $a$ 可以被表示为 $a_1 \times 10^{n-1}+a_2 \times 10^{n-2}+\dots+a_n \times 10^0$

因为 $(a \times b) \bmod c=(a \bmod c \times b \bmod c) \bmod c$，则有 $10^k \bmod 9=(10 \bmod 9)^k \bmod 9=1$。

又因为 $(a+b) \bmod c=(a \bmod c+b \bmod c) \bmod c$

从而 $a \equiv (a_1+a_2+\dots+a_n) \pmod 9$。

这样一来，题面中的 $S(x) \equiv x \pmod 9$。从而我们相当于只需求出斐波那契数列的每一项对 $9$ 取模的结果，然后做前缀和即可完成本题。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <queue>
#include <vector>

using namespace std;

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

int t,fib[1000055];

int main()
{
	cin >> t;
	fib[1]=fib[2]=1;
	for (int i=3;i<=1000050;i++)
		fib[i]=(fib[i-2]+fib[i-1])%9;
	for (int i=1;i<=1000050;i++)
		fib[i]=(fib[i]+fib[i-1])%9;
	while (t--)
	{
		int n;
		cin >> n;
		cout << fib[n] << endl;
	}
	return 0;
}