题解 P8377 [PFOI Round1] 暴龙的火锅

chen_zhe · 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;
}