自动搬运

查看原文

来自洛谷，原作者为

	Thomas_Cat 越学越菜。

搬运于2025-08-24 22:28:44，当前版本为作者最后更新于2021-08-20 19:25:49，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

对于这一题对于 $100\%$ 的数据 $1 \le k \le 10^{12}$ 则显然不会是暴力打解了，一定是有规律的，因此可以从这方面去考虑。

Subtask 1

显然 $1 \le k \le 10^6$ 只需要暴力枚举即可，复杂度 $\mathcal{O}(n)$，注意在计算 $a_i=a_{i-1} \times a_{i-2} \bmod 10$ 的时候如果单纯按原式代入计算 $a_i$ 的话那么在后面可能会爆 $\texttt{int}$，所以注意：

因为只计算个位数，只用算出 $a_{i-1} \bmod 10, a_{i-2} \bmod 10$ （也就是个位数即可），应该把式子变成：

$$a_i=(a_{i-1}\bmod 10) \times (a_{i-2}\bmod 10) \bmod 10 $$

直接打暴力即可：（$30 pts$）

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,m,k;
	cin>>n>>m>>k;
	int a[100005];
	a[1]=n,a[2]=m;
	for(int i=3;i<=k;i++)
		a[i]=(a[i-1]%10*a[i-2]%10)%10;//按照式子计算得出答案
	cout<<a[k];//最后输出即可
	return 0;
}

Subtask 2

显然不能打暴力了，对于 $1 \le k \le 10^{12}$ 需要找规律，因此我们尝试枚举部分情况的结果：

下表中 $k$ 均为 $15$。

$(n,m)$	$a_1$	$a_2$	$a_3$	$a_4$	$a_5$	$a_6$	$a_7$	$a_8$	$a_9$	$a_{10}$	$a_{11}$	$a_{12}$	$a_{13}$	$a_{14}$	$a_{15}$
$(4,9)$	$4$	$9$	$6$	$4$		$6$	$4$		$6$	$4$		$6$	$4$		$6$
$(7,8)$	$7$	$8$		$8$		$4$	$2$	$8$		$8$		$4$	$2$	$8$
$(3,9)$	$3$	$9$	$7$	$3$	$1$	$3$		$9$	$7$	$3$	$1$	$3$		$9$	$7$
$(6,8)$	$6$	$8$		$4$	$2$	$8$	$6$	$8$		$4$	$2$	$8$	$6$	$8$
$(7,3)$	$7$	$3$	$1$	$3$		$9$	$7$	$3$	$1$	$3$		$9$	$7$	$3$	$1$

上图中就是几个数对按照题目要求得出的 $a_1 \sim a_{15}$ 数。

在图中：

$(n,m)$	$a_1$	$a_2$	$a_3$	$a_4$	$a_5$	$a_6$	$a_7$	$a_8$	$a_9$	$a_{10}$	$a_{11}$	$a_{12}$	$a_{13}$	$a_{14}$	$a_{15}$
$(4,9)$	$4$	$9$	$\color{red}6$	$\color{red}4$		$\color{red}6$	$\color{red}4$		$\color{purple}6$	$\color{purple}4$		$\color{purple}6$	$\color{purple}4$		$6$
$(7,8)$	$7$	$8$		$\color{red}8$		$\color{red}4$	$\color{red}2$	$\color{red}8$		$\color{purple}8$		$\color{purple}4$	$\color{purple}2$	$\color{purple}8$
$(3,9)$	$3$	$9$	$\color{red}7$	$\color{red}3$	$\color{red}1$	$\color{red}3$		$\color{red}9$	$\color{purple}7$	$\color{purple}3$	$\color{purple}1$	$\color{purple}3$		$\color{purple}9$	$7$
$(6,8)$	$6$	$8$	$\color{red}8$	$\color{red}4$	$\color{red}2$	$\color{red}8$	$\color{red}6$	$\color{red}8$	$\color{purple}8$	$\color{purple}4$	$\color{purple}2$	$\color{purple}8$	$\color{purple}6$	$\color{purple}8$	$8$
$(7,3)$	$7$	$3$	$\color{red}1$	$\color{red}3$		$\color{red}9$	$\color{red}7$	$\color{red}3$	$\color{purple}1$	$\color{purple}3$		$\color{purple}9$	$\color{purple}7$	$\color{purple}3$	$1$

我们可以发现$\color{red}红色$部分和$\color{purple}紫色$部分的数字是完全相同的，不妨猜测所有数列都以 $6$ 次为循环。

根据这个思路我们用 $k$ 来看看，因为 $a_1,a_2$ 不考虑在数列以内，因此对于 $k$ 在循环中的点的公式为 $ans=(k-3) \bmod 6 +3$ ，因此代入计算即可。

#include<bits/stdc++.h>
using namespace std;
int main(){
	long long n,m,k;
	cin>>n>>m>>k;
	int a[10],b[7];
	a[1]=n,a[2]=m;//a1,a2按照前面算出来，因为数列中不包含
	for(int i=3;i<=9;i++)//循环
		a[i]=(a[i-1]%10*a[i-2]%10)%10;//按照前面算出第一个数列也就是六次循环算出的结果
    cout<<a[(k-3)%6+3];//代入公式计算算出即可
	return 0;
}

令：如果遇到相乘 $a_2,a_3$ 为 $1,5,6$，只需输出 $1,5,6$ 即可；如果遇到 $a_i=0$ 输出 $0$ 即可。

综上，求解方法为：

$$a_i=(a_{i-1}\bmod 10) \times (a_{i-2}\bmod 10) \bmod 10 $$

令：

$$g(x)=\min_{1 \le i \le x,a_i \in [1,9]} a$$ $$r(x)=\max_{1 \le i \le x,a_i \in [1,9]} a$$

则：

$$\Longrightarrow ans = \begin{cases}g(x)\in\{0\}&ans=0\\r(2),r(3) \in \{5\}&ans=5\\r(2),r(3) \in \{6\}&ans=6\\else&ans=a_{(k-3) \bmod 6 +3}\end{cases} $$

亲测，稳过