题解 P7840 【「PMOI-4」人赢】

Thomas_Cat · 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 （也就是个位数即可），应该把式子变成：

直接打暴力即可：（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。

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

在图中：

我们可以发现\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 即可。

综上，求解方法为：

令：

则：

亲测，稳过