题解：P1965 [NOIP2013 提高组] 转圈游戏

_SLL_ · 2025-01-07 22:23:54 · 题解

思路

规律很简单,答案就是：(x+10^km) \bmod n 。 但这个数很大，要边算边取余，所以要用到快速幂。

什么是快速幂？

快速幂是一种高效计算大数幂的方法，其核心思想是将幂次拆分成二进制形式，通过平方和乘法逐步计算结果,从而显著降低运算量‌。快速幂的时间复杂度为 O(\log_2n) ，与朴素的 O(n) 相比效率有了极大的提高‌。

——摘自百度搜索。

AC code

#include<bits/stdc++.h>
using namespace std;
int n,m,k,x;
int fpow(int x,int p){
    int res=1;
    while(p>0){
        if(p % 2) res = res * x % p;
        p >>= 1;
        x = x * x % p;
    }
    return res;
}
int main(){
    cin>>n>>m>>k>>x;
    long long sum=((fpow(10,k) % n * m) % n + x) % n;
    cout << sum << endl;
    return 0;
}

求管理员大大过吧QAQ。