洛谷 P1965 转圈游戏

目录

• $code$

---

题目

p1965 转圈游戏

思路

数论。题目就是让你判断一下第$x$个人走了$m \times 10^k$步之后到了哪里。总共走的步数为$m \times 10^k$直接走肯定会tle，对$n$取模之后再走就好了。

$code$

#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
#define int long long
using namespace std;
int n,m,k,x;
int qpow(int a,int b,int mod){
    int ans=1,base=a;
    while(b){
        if(b&1) ans=ans*base%mod;
        base=base*base%mod;
        b>>=1;
    }
    return ans;
}
inline void read(int &t){
    int x=0;bool f=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=!f;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    t=f?-x:x;
}

signed main(){
    read(n),read(m);
    read(k),read(x);
    m%=n;
    int qwq=qpow(10,k,n);
    int ans=m*qwq%n;
    while(ans--){
        x++;
        if(x==n) x=0;
    }
    cout<<x<<endl;
    return 0;
}