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

Cripple_Abyss · 2021-08-24 12:39:25 · 题解

题目传送门

Description ：

• 已知 a_1 = n ，a_2 = m 且 a_i (i>2) = a_{i-1} * a_{i-2}\ mod\ 10 。

• 给定 k , 求 a_k 的值 。

Solution :

• 根据抽屉原理知 ：a_i 的值必有循环 。

• 暴力模拟找循环节 。

• 设从 a_{st} 的位置开始循环，到 a_{ed} 的停止循环，循环的值存在数组 ans 中 （ans_0 = a_{ed}）。

• p=(k-st+1)\ mod\ (ed-st+1)$ , $a_k=ans_{p}

Code：

#include <cstdio>
typedef long long ll;
inline void in(ll &x) {
    x=0;
    ll f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9') {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    x*=f;
}
inline void out(ll x) {
    if (x<0) putchar('-'),x=-x;
    if (x>9) out(x/10);
    putchar(x%10+'0');
}
ll n,m,k,a[100005],st,ed,len,ans[1000005],x;
int main() {
    in(a[1]),in(a[2]),in(k);
    for (int i=3; i<=k; ++i) {
        a[i]=(a[i-1]*a[i-2])%10;
        for (int j=2; j<i; ++j) {
            if (a[j]==a[i]&&a[j-1]==a[i-1]) {
                st=j-1;
                ed=i-2;
                break;
            }
        }
        if (st) break;
    }
    if (!st) out(a[k]);
    else {
        len=ed-st+1;
        for (int i=1,p=st; i<len; ++i,++p) ans[i]=a[p];
        ans[0]=a[ed];
        x=(k-st+1)%len;
        out(ans[x]);
    }
    return 0;
}