快速幂学习笔记

接下来讲的快速幂并非二进制版本，而是二分幂

快速幂

有些时候，我们需要求一个数的多次幂，假如数字非常大，这个时候，手写的求幂函数和cmath库中自带的pow函数就显得有些慢了。接下来我要讲一种算法可以在$O(\log n)$的时间内求出一个数的多次幂。

翻翻初中数学课本，我们可以发现如下公式：

$$x^y \times x^z = x^{y+z}$$

应用到OI上来，因为C++ int有精度误差，所以我们要分情况讨论。

如果$y$是偶数：

$$x^y = x^{\lfloor \frac y 2 \rfloor + \lfloor \frac y 2 \rfloor} = x^{\lfloor \frac y 2 \rfloor} \times x^{\lfloor \frac y 2 \rfloor} $$

如果$y$是奇数：

$$x^y = x^{\lfloor \frac y 2 \rfloor} \times x^{\lfloor \frac y 2 \rfloor} \times x$$

代码

int slow_pow(int x, int y)
{
    int ans = 1;
    while (y > 0)
    {
        if (y % 1 == 1)
            ans = ans * x;
        x = x * x;
        y /= 2;
    }
    return ans;
}

例题 NOIP2013 转圈游戏

题目描述

点我传送

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

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

题解

我们不难推出以下“柿子”：

$$(m \times 10 ^k + x) \mod n$$

一个快速幂搞定。

#include <bits/stdc++.h>
using std::cin;
using std::cout;

#define endl '\n'
#define R register

long long n, m, k, x;

long long _pow(long long y, long long x,long long mod)
{
    long long ans = 1;
    while(x > 0)
    {
        if(x & 1)
            ans = ans * y % mod;
        y = y * y % mod;
        x >>= 1;
    }
    return ans % mod;
}

int main()
{
#ifdef ONLINE_JUDGE
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#endif

    cin >> n >> m >> k >> x;

    cout << (m % n * _pow(10, k, n) % n + x % n) % n;
    return 0;
}