题解 P1965 【转圈游戏】

· · 题解

挺多人是推公式然后快速幂直接求。

我也用了快速幂，但是因为本人蒟蒻，推不出公式，就用了另一个方法（呵呵）

推出从当前的x从开始移动到回到原来位置经过的每个位置，记为序列a。

我们要进行10^k次的移动，那么可以将序列a作为一个周期，设序列a中共有lena个元素，然后直接用快速幂求出temp = 10^k mod lena，最后要输出的就是a_{temp}。

复杂度的话可以这么估测：

之前所推出的序列推出所用的复杂度可以用找规律的方法解出来：

data1$ $:$ $10$ $3$ $4$ $5

周期：4 7 0 3 6 9 2 5 8 1

data2$ $:$ $10$ $2$ $4$ $5

周期：4 6 8 0 2

可得周期长度为：n / gcd(n,m)

根据数据就能够知道这里的复杂度为O(gcd(n,m))。

快速幂的复杂度是O(log k)，总最大复杂度应当是O(gcd(n,m) + log k)

注：此处的gcd(n,m)是按我的程序中实现来规划复杂度的，不一定是最好的实现方法。

上代码：

#include<cstdio>
using namespace std;
int n,m,k,x,use,a[1000001];
int f(int p){
    if(p==0) return 1;
    int tmp=f(p/2)%use;
    tmp=(tmp*tmp)%use;
    if(p%2==1) tmp=(tmp*10)%use;
    return tmp;
}
int find(int n,int m){
    int ans;
    for(int i=1;i<=m;i++){
        if(m%i==0&&n%i==0){
            ans=i;
        }
    }
    return n/ans;
}
int main(){
    scanf("%d%d%d%d",&n,&m,&k,&x);
    int temp=0,chan=x;
    use=find(n,m);
    a[temp]=x;
    while(temp<=use-1){
        chan=(chan+m)%n;
        temp++;
        a[temp]=chan;
    }
    int l=f(k);
    printf("%d",a[l]);
    return 0;
}