洛谷 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;
}