快 速 幂

[NOIP2013 提高组] 转圈游戏 题目描述

n n n 个小伙伴（编号从 $0 $到 n − 1 n-1 n−1）围坐一圈玩游戏。按照顺时针方向给 n n n个位置编号，从 0 0 0 到 n − 1 n-1 n−1。最初，第 $0 $号小伙伴在第 0 0 0号位置，第 $1 $号小伙伴在第 1 1 1 号位置，……，依此类推。游戏规则如下：每一轮第 0 0 0 号位置上的小伙伴顺时针走到第 m m m 号位置，第 1 1 1号位置小伙伴走到第 m + 1 m+1 m+1 号位置，……，依此类推，第n − m号位置上的小伙伴走到第 0 号位置，第 n ∼ m + 1 n \sim m+1 n∼m+1 号位置上的小伙伴走到第 1 1 1 号位置，……，第 n − 1 n-1 n−1 号位置上的小伙伴顺时针走到第 m − 1 m-1 m−1 号位置。

现在，一共进行了 1 0 k 10^k 10k轮，请问 x x x号小伙伴最后走到了第几号位置。

输入格式

共 1 1 1行，包含 4 4 4 个整数 n , m , k , x n,m,k,x n,m,k,x，每两个整数之间用一个空格隔开。

输出格式

1 1 1个整数，表示 1 0 k 10^k 10k轮后 x x x 号小伙伴所在的位置编号。

样例 #1 样例输入

10 3 4 5

样例输出

5

提示

对于 30 % 30\% 30%的数据， 0 < k < 7 0 < k < 7 0<k<7；

对于 80 % 80\% 80%的数据， 0 < k < 1 0 7 0 < k < 10^7 0<k<107；

对于 100 % 100\% 100%的数据， 1 < n < 1 , 000 , 000 , 0 < m < n , 1 ≤ x ≤ n , 0 < k < 1 0 9 1 1<n<1,000,000,0<m<n,1≤x≤n,0<k<109。

分析

比赛的时候第一个思路也是快速幂，但是它这个数据太大，感觉有点看晕了。感觉就是对快速幂的理解不够深。

快速幂就是求 a b a^b ab 时，当这个数的 b 十分大时采取的办法：变乘边模。因为 a ^ b 可以表示为 a b − c ∗ a c a^{b-c}*a^{c} ab−c∗ac 这是显然的吧。然后如何拆分呢，可以用二进制数来表示 b 。如何求一个数的二进制数？

int a[100];//存二进制数
int cnt;//下标
void qmi(int b)
{
	while(b)
    {
        b[++ cnt] = b % 2;
        b /= 2;
    }
    return;
}

我相信这段应该是没问题的。思路也就是这样：模一个数，若为 1 那么这个位置上用二进制表达就是 1 。感觉有点抽象，比如 5 。

• 5 % 2 = 1。第一位是 1 吧 。再 / 2 = 2
• 2 % 2 = 0。第二位是 0 。2 / 2 = 1
• 1 % 2 = 1。第三位是 1

5 用二进制数表示为 101。这上面是一个道理。

既然可以把 k 拆开 ，那就可以分步处理了。又因 a b − c ∗ a c a^{b-c}*a^{c} ab−c∗ac，回看题面 ，a 就相当于 10 （轮 1 0 k 10 ^ k 10k 轮），k 就相当于 b。其实刚接触快速幂时，我想用 pow 函数写，但是 pow 返回的数范围太小，所以要换一种办法：a 乘以自己，表示下一位。a 初始为 10 ，相当于 1 0 1 10 ^ 1 101。a *= a，变为 1 0 2 10 ^ 2 102 。 a *= a，变为 1 0 4 10 ^ 4 104 ，1 2 4 ，是否就是二进制的变化。所以 a 的变化还将 k 囊括进来了。

看一下代码

#include
using namespace std;

int n, m, k, x, ans = 1, b = 10;

int main()
{
	scanf("%d%d%d%d", &n, &m, &k, &x);
	ans *= m;
	ans %= n;
	while(k)
	{
		if(k % 2 == 1)
			ans = ans * b % n;
		b *= b;
		b %= n;
		k >>= 1;
	}
	ans += x % n;
	ans %= n;
	printf("%d", ans);
	return 0;
}

真题的变量并不会给得很明显，要找到 一 一 对应关系。

这里还要会的一个公式是 （ a + b ）% mod = a % mod + b % mod.
2022-5-22 21:27:58