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

思路

规律很简单,答案就是：

(x+10^km) \bmod n

。但这个数很大，要边算边取余，所以要用到快速幂。

什么是快速幂？

快速幂是一种高效计算大数幂的方法，其核心思想是将幂次拆分成二进制形式，通过平方和乘法逐步计算结果,从而显著降低运算量‌。快速幂的时间复杂度为

O(\log_2n)

，与朴素的

O(n)

相比效率有了极大的提高‌。

——摘自百度搜索。

AC code

CPP

#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。

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

文章操作

思路

什么是快速幂？

AC code

相关推荐

评论

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