题解 P1965 【转圈游戏】

koosi · 2018-09-12 12:59:07 · 题解

快速幂模板题，我们可以发现一个人第二次走到初始位置位置的时间t=n*m/gcd(n,m)/m也就是n/gcd(n,m)，接下来就是裸的快速幂了。

# include <cstdio>
# include <iostream>
# define re register  int
using namespace std;
inline  int gcd (int  x,int y){
    if(y==0)    return x;
    else return gcd(y,x%y); 
}//欧几里得求最大公约数
inline int quick(int k,int mod){
    re a=10,s=1;
    //位运算的快速幂
    while(k){
        if(k&1) s=(s%mod*a%mod)%mod;
        a=(a%mod*a%mod)%mod;
        k>>=1;  
    } return s;
}
int main (){
    re n,m,k,x;
    scanf("%d%d%d%d",&n,&m,&k,&x);
    re T=n/gcd(n,m);//周期
    re mod=quick(k,T);//去掉重复走之后的步数
    for(re i=1;i<=mod;++i){
        x=(x+m)%n;//直接取模就好，如果下标是1~n则要先全部减1
    }
    printf("%d",x); return 0;
}