问题B - 有趣的 3721 数

题目描述

原题面

有一天，小明发现了一个有趣的现象，$8$ 除以 $3$ 余 $2$，$8$ 除以 $7$ 余 $1$，他把这种除以 $3$ 余 $2$ 同时除以 $7$ 余 $1$ 的数称为“$\texttt{3721}$”。请编程实现：输入 $k$ 的值，请输出前 $k$ 个和第 $k$ 个“$\texttt{3721}$”数（$1\le k\le 1000$）。

输入要求

一行，一个整数，表示 $k$ 的值。

输出要求

输出共两行。第一行输出前 $k$ 个“$\texttt{3721}$”数，第二行输出第 $k$ 个“$\texttt{3721}$”数。

样例

8 29 50 71
71

解法

暴力枚举并判断

通过枚举每一个数并进行判断是否符合条件，计算每一个数的时间复杂度为 $O(n)$。

数学方法

如果注意力惊人，通过观察给定的数列（记为 $\{a_n\}$）的前 $4$ 项：$8, 29, 50, 71$，不难发现数列 $\{a_n\}$ 很可能是一个以 $8$ 为首项，$21$ 为公差的等差数列。使用等差数列通项公式即可 $O(1)$ 地计算第 $n$ 位的值。

严谨的数学证明如下：

我们已知以下同余关系：

\[ \left\{\begin{matrix} x \equiv 2 \pmod{3} \\ x \equiv 1 \pmod{7} \end{matrix}\right. \]

令 $ x = 7k + 1, k \in \mathbb{Z} $，则有：

\[ \begin{align*} 7k + 1 \equiv 2 \pmod{3} \\ k + 1 \equiv 2 \pmod{3} \\ k \equiv 1 \pmod{3} \end{align*} \]

令 $ k = 3m + 1, m \in \mathbb{Z} $，因此：

\[ x = 7k + 1 = 7(3m + 1) + 1 = 21m + 8 \]

最终得出 $ x = 21m + 8, m \in \mathbb{Z} $。

拓展

类似题目：洛谷 P11144 「SFMOI Round I」Strange Madoka Game，
相应解法：洛谷十月月赛官方题解

更多同余相关的算法参考：模意义下的运算、中国剩余定理。

#include <bits/stdc++.h>
#define lli long long int
using namespace std;

int main() {
    lli n;
    scanf("%lld", &n);
    for(lli i = 1; i <= n; i ++)
        printf("%lld ", 21 * (i - 1) + 8);
    printf("\n%lld", 21 * (n - 1) + 8);
    return 0;
}